题目分析:
本题目可以看做是01背包和多重背包的一个结合题目。
解答方法有两种:
1. 因为数据量较小可以将各个背包物品进行分配,使成为01背包问题,但是这样使用二维数组的话是会tle的,
因为f[10010][100]这个数据范围在1e9了,是不行的。只能转化为一维数组来解决
2. 直接运算。这个方法一定要注意不可以写成:
f[i][j]=f[i-1][j];
for(int k=1;k<=s[i];k++){
f[i][j]=max(f[i][j],f[i-1][j-v[i]+w[i]);
或者是:
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
等形式。
这点就是01背包和多重背包,完全背包几类背包问题的区别。
代码1:
#include<iostream>
using namespace std;
const int N=10010;
int f[N];
int v[N];
int w[N];
int s[N];
int main(){
int m,n;
cin>>m>>n;
int t;
for( t=1;t<=m;t++){
cin>>v[t]>>w[t]>>s[t];
}
for(int l=1;l<=m;l++){
for(int j=1;j<s[l];j++){
v[t]=v[l];
w[t]=w[l];
++t;
}
}
for(int i=1;i<t;i++){
for(int j=n;j>=v[i];j--){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[n]<<endl;
return 0;
}
代码2:
#include<iostream>
using namespace std;
const int N=1100;
int f[N][N];
int w[N];
int v[N];
int s[N];
int main(){
int m,n;
cin>>m>>n;
for(int i=1;i<=m;i++){
cin>>v[i]>>w[i]>>s[i]; }
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
for(int k=0;(k<=s[i])&&(k*v[i]<=j);k++){
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<<f[m][n]<<endl;
return 0;
}