算法思路
朴素DP
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main()
{
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 = 0; j <= m; j++)
for(int k = 0; k * v[i] <= j; k++)
{
f[i][j] = max(f[i][j],f[i - 1][j - k * v[i]] + k * w[i]);
}
cout << f[n][m] << endl;
return 0;
}
dp优化
注意此时的 f[i][j] = max(f[i][j],f[i][j - v[i]] + w[i]);
用到的是第i层数据
所以从小到大更新正好可以更新成第i层的数据
故代码为
int main()
{
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 = v[i]; j <= m; j++)
f[j] = max(f[j],f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}