AcWing 2. 01背包问题
原题链接
简单
作者:
虹之间
,
2020-11-03 08:26:52
,
所有人可见
,
阅读 263
方法一:二维dp
- f[i][j]表示只使用前i个物品且总体积为j的情况下能得到的最大价值
- f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w[i])
#include <iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N], w[N];
int main()
{
int n, m; cin >> n >> m;
for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
int res = 0;
for(int i = 1; i <= n; i ++ ) res = max(res, f[i][m]);
cout << res << endl;
return 0;
}
方法二:一维dp
#include <iostream>
using namespace std;
const int N = 1010;
int f[N];
int main()
{
int n, m; cin >> n >> m;
for(int i = 1; i <= n; i ++ ){
int v, w; cin >> v >> w;
for(int j = m; j >= v; j -- )
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}