51nod oj 1086 背包问题 V2 【多重背包问题】

题目链接：1086

多重背包转01背包---

代码：

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int bao[50050]; int w[10000],p[100000]; int main() { int n,ww; scanf("%d%d",&n,&ww); int kp=0;int a,b,c; for (int i=0;i<n;i++) { scanf("%d%d%d",&a,&b,&c); for (int i=1;c;i*=2) { if (c>=i) { w[kp]=a*i; p[kp++]=b*i; c-=i; } else { w[kp]=a*c; p[kp++]=b*c; c=0; } } } memset(bao,0,sizeof(bao)); for (int i=0;i<kp;i++) for (int j=ww;j>=w[i];j--) bao[j]=max(bao[j-w[i]]+p[i],bao[j]); printf("%d\n",bao[ww]); return 0; }