51Nod 1086【背包问题 V2】

第1行，2个整数，N和W中间用空格隔开。N为物品的种类，W为背包的容量。(1 <= N <= 100，1 <= W <= 50000)
第2 - N + 1行，每行3个整数，Wi，Pi和Ci分别是物品体积、价值和数量。(1 <= Wi, Pi <= 10000， 1 <= Ci <= 200)

输出可以容纳的最大价值。

3 6
2 2 5
3 3 8
1 4 1

9

看到这道题第一感觉就是0 1背包的变形，我把他转化成0 1背包不就解决了吗。然而我还是too young too simple.....

被超时闪瞎了眼，然后就百度呗，发现这是什么多重背包（我还没学），不过大佬讲的就是好

这个问题是一道常见的多重背包问题，和完全背包相似，可以转化为01背包问题，但是转化过程中，不能简单的将第i种拆分成ci[i]个物品，要利用一些数学知识来优化，应拆分为1、2、4……c[i]-sum种，sum为前边拆分的和。（转自：点击打开链接）

附上我的超时代码和大佬代码

/* #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int dp[200100]; int w[100100],p[100100],c[2100]; int main() {int n,W;scanf("%d%d",&n,&W);int t=n,sum=0;for(int i=0;i<n;i++){scanf("%d %d %d",&w[i],&p[i],&c[i]);sum=sum+c[i]-1;for(int j=t;j<n+sum;j++,t++) //从n往后存放重复的物品 {w[j]=w[i];p[j]=p[i];}}int ans=0; for(int i=0;i<t;i++) { for(int k=W;k>=w[i];k--) { dp[k] = max( dp[k], dp[ k-w[i] ] + p[i] ); ans=max( ans, dp[k] );} }printf("%d\n",ans); return 0; } */ #include <iostream> #include <cstring>using namespace std;const int MAXN = 101; const int SIZE = 50001;int dp[SIZE]; int volume[MAXN], value[MAXN], c[MAXN]; int n, v; // 总物品数，背包容量// 01背包 void ZeroOnepark(int val, int vol) {for (int j = v ; j >= vol; j--){dp[j] = max(dp[j], dp[j - vol] + val);} }// 完全背包 void Completepark(int val, int vol) {for (int j = vol; j <= v; j++){dp[j] = max(dp[j], dp[j - vol] + val);} }// 多重背包 void Multiplepark(int val, int vol, int amount) {if (vol * amount >= v){Completepark(val, vol);}else{int k = 1;while (k < amount){ZeroOnepark(k * val, k * vol);amount -= k;k <<= 1;}if (amount > 0){ZeroOnepark(amount * val, amount * vol);}} }int main() {while (cin >> n >> v){for (int i = 1 ; i <= n ; i++){cin >> volume[i] >> value[i] >> c[i]; // 费用，价值，数量}memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; i++){Multiplepark(value[i], volume[i], c[i]);}cout << dp[v] << endl;}return 0; }