混合背包问题
混合背包问题结合了01,完全,多重背包问题,只需要在遍历到每一个物品后判断一下该物品是那种类型的背包问题,再进行循环,求该行元素即可
#include<iostream>
using namespace std;
const int N=1010;
int v[N],w[N],s[N];
int f[N];
int n,m;
int main(){
cin>>n>>m;
int v,w,s;
for(int i=1;i<=n;i++){
cin>>v>>w>>s;
if(!s){
for(int j=v;j<=m;j++){
f[j] = max(f[j],f[j-v]+w);
}
}
else{
if(s==-1)s=1;
for(int k=1;k<=s;k*=2){
for(int j=m;j>=v*k;j--){
f[j]=max(f[j],f[j-k*v]+k*w);
}
s-=k;
}
if(s){
for(int j=m;j>=s*v;j--){
f[j]=max(f[j],f[j-s*v]+w*s);
}
}
}
}
cout<<f[m];
return 0;
}