完全背包和01背包差别:
完全背包是一件物品可以选多次,01背包是一件物品是能选一次;
核心代码区别:
完全背包
for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{
f[i][j] = f[i-1][j];
if(j-v[i]>=0)
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
01背包
for(int i = 1 ; i <= n ; i++)
for(int j = 0 ; j <= m ; j ++)
{
f[i][j] = f[i-1][j];
if(j-v[i]>=0)
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
两个代码其实只有一句不同(注意下标),01背包的第一位物品维是i-1f[i-1][],而完全背包是f[i],因此巧计,01背包有1,所以要减1,完全背包无1,所以不用减1
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包
f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题
完整代码:
#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1010;
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++){
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];
return 0;
}