普通写法
#include<iostream>
using namespace std;
const int N = 1e3+10;
int v[N],w[N],f[N][N];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;++i)
for(int j=0;j<=m;++j)
{
//先选择f[1~(i-1),j)
f[i][j] = f[i-1][j];
//当j >= v[i]时
if(j >= v[i])
//计算出 减掉v[i]权重后的最大值+w[i] 是否更大
f[i][j] = max(f[i][j],f[i-1][j - v[i]] + w[i]);
}
cout << f[n][m];
return 0;
}
优化
- 因为f(i,j) 是滚动数组,所以可以优化为一维数组
#include<iostream>
using namespace std;
const int N = 1e3+10;
int v[N],w[N],f[N];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;++i)
/*
1.此处不能按从小到大遍历
2.因为 当前数组 需要根据上一次的结果更新现有结果
3.所以j-v[i] 会先将当前行中叫小的i先更新
*/
for(int j = m;j>=v[i];--j)
{
f[j] = max(f[j],f[j - v[i]] + w[i]);
}
cout << f[m];
return 0;
}