中心思想:所有只从前i个物品中选,总体积不超过j的方案的集合
1.01背包:f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
2.完全背包:f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
朴素写法
#include<bits/stdc++.h>
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=1;j<=m;j++){
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
cout<<f[n][m]<<endl;
return 0;
}
空间优化后的写法
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];
int f[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=v[i];j<=m;j++){//直接从v[j]开始循环
//f[j]=f[j];可以去掉
//f[i][j]=f[i-1][j];
f[j]=max(f[j],f[j-v[i]]+w[i]);
//f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
cout<<f[m]<<endl;
return 0;
}