题目描述
有 N 种物品和一个容量是 V的背包。
物品一共有三类:
第一类物品只能用1次(01背包);
第二类物品可以用无限次(完全背包);
第三类物品最多只能用 si次(多重背包);
每种体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
样例
输入
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出
8
混合算法
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n,V;
struct kk{int w,v,m;};
kk a[1001];
int f[20001];
void completebag(int v,int w){
for(register int i=v;i<=V;++i)
f[i]=max(f[i],f[i-v]+w);
return;
}
void zeronebag(int v,int w){
for(register int i=V;i>=v;--i)
f[i]=max(f[i],f[i-v]+w);
return;
}
void multiplebag(int v,int w,int m){
if(m*v>V){
completebag(v,w);
return;
}
int k=1;
while(k<=m){
zeronebag(v*k,w*k);
m-=k;
k*=2;
}
zeronebag(v*m,w*m);
return;
}
int main() {
scanf("%d%d",&n,&V);
for(register int i=1;i<=n;++i)
scanf("%d%d%d",&a[i].v,&a[i].w,&a[i].m);
memset(f,0x0,sizeof(f));
for(register int i=1;i<=n;++i){
if(a[i].m==-1) zeronebag(a[i].v,a[i].w);
if(a[i].m==0) completebag(a[i].v,a[i].w);
if(a[i].m>0) multiplebag(a[i].v,a[i].w,a[i].m);
}
printf("%d\n",f[V]);
return 0;
}