首页 > 代码库 > Multiplepack coming~^.^
Multiplepack coming~^.^
多重背包:
基本思路:
先来看一个引例:有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。这种类型的背包问题的特点是:每件物品的件数有限。
和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件,取1件„„取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值,则有状态转移方程:f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]} 完全背包中k的范围是(0<=k<=v/c[i]). 复杂度是O(V*Σn[i]),
代码与完全背包的区别仅在内部循环上由
1 | for(k = 1; k <= j/weight[i]; ++k) |
变为
1 | for(k = 1; k <=n[i] && k<=j/weight[i]; ++k) |
多重背包二进制拆分实现
跟完全背包一样的道理,利用二进制的思想将n[i]件物品i拆分成若干件物品,目的是在0-n[i]中的任何数字都能用这若干件物品代换,另外,超过n[i]件的策略是不允许的。
方法是将物品i分成若干件,其中每一件物品都有一个系数,这件物品的费用和价值都是原来的费用和价值乘以这个系数,使得这些系数分别为1,2,4,…,2^(k-1),n[i]-2^k+1,且k满足n[i]-2^k+1>0的最大整数。例如,n[i]=13,就将该物品拆成系数为1、2、4、6的四件物品。分成的这几件物品的系数和为n[i],表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数,均可以用若干个系数的和表示。
1 #include <iostream> 2 using namespace std; 3 4 /* 多重背包 二进制拆分 5 * Time Complexity 大于O(N*V) 6 * Space Complexity O(N*V) 7 * 设 V <= 200 N <= 10 ,拆分后 物品总数 < 50 8 * 每件物品有 log n[i]种状态 9 */10 11 int maxV[201];12 int weight[50]; /* 记录拆分后物体重量 */13 int value[50]; /* 记录拆分后物体价值 */14 int V, N;15 16 void main()17 {18 int i, j;19 scanf("%d %d",&V, &N);20 int weig, val, num;21 int count = 0;22 23 for(i = 0; i < N; ++i)24 {25 scanf("%d %d %d",&weig,&val,&num);26 27 for(j = 1; j <= num; j <= 1) // 二进制拆分28 {29 weight[count] = j * weig;30 value[count++] = j * val;31 num -= j;32 }33 if(num > 0)34 {35 weight[count] = num * weig;36 value[count++] = num * val;37 }38 }39 for(i = 0; i < count; ++i) // 使用01背包40 {41 for(j = V; j >= weight[i]; --j)42 {43 int tmp = maxV[j-weight[i]] + value[i];44 maxV[j] = maxV[j] > tmp ? maxV[j] : tmp;45 }46 }47 printf("%d",maxV[V]);48 }49 50 /*51 【输入样例】52 4 2053 3 9 354 5 9 155 9 4 256 8 1 357 【输出样例】58 4759 */
下面给出O(log amount)时间处理一件多重背包中物品的过程,其中amount表示物品的数量:
1 void multiplepack(int cost, int weight, int amount) 2 { 3 if(cost*amount>=V) 4 cmpletepack(cost,weight); 5 else 6 { 7 int k=1; 8 while(k<amount) 9 {10 zeroonepack(k*cost,k*weight);11 amount-= k;12 k=k*2;13 }14 zeroonepack(amount*cost,amount*weight);15 }16 }
总结完啦~要回家了已经做不进去题了~噶呜~但我还在坚持每天更新博客~*。*