（六）多重背包-- 二进制位压缩解法--一维数组解析
//解法一：二进制位压缩解法。 #include <stdio.h> #include<iostream> using namespace std; #include <iomanip> #define MAX 10000 int g_All_V; int f[MAX]; void print(); int max( int x, int y ) { x=x>y?x:y; return x; } void ComepletePack( int single_Value, int single_V ) // 完全背包问题的算法，要想详细了解，见背包九讲第二讲。 { cout<<"void
ComepletePack( int single_Value, int single_V )"<<endl; int j; for(j=single_V; j<=g_All_V; j++ ) f[j]=max( f[j], f[j-single_V]+single_Value ); print(); cout<<"void
ComepletePack( int single_Value, int single_V ) end end end end end end end !!!"<<endl; return ; } void ZeroOnePack( int single_Value, int single_V ) // 01背包问题的算法，要想详细了解，见背包九讲第一讲。 { cout<<"void
ZeroOnePack( int single_Value, int single_V )"<<endl; ; int j; for(j=g_All_V; j>=single_V; j-- ) { f[j]=max( f[j], f[j-single_V]+single_Value ); } print(); cout<<"void
ZeroOnePack( int single_Value, int single_V ) end end end end end end end
end!!!"<<endl; } //g_All_V：相当于 用于装东西的 总体积，挖金矿总人数， //single_V：单个物品的体积 //single_Value：单个物品的价值 //single_Max_Num: 物品可用的最大个数 void MultiplePack ( int single_Value, int single_V, int single_Max_Num ) //
多重背包问题算法，要想详细了解，见背包九讲第三讲。 { cout<<"void
MultiplePack ( int single_Value, int single_V, int single_Max_Num )"<<endl; /* 当
single_V*single_Max_Num>g_All_V, 理解为 当对于某个种类的 单个物品的体积single_V
乘以 物品可用的最大个数
single_Max_Num ，大于 用于装东西的 总体积g_All_V 也就是可以理解为对这种类型的物品可以无限的增加，因为对于本题来说 这个种类的物品个数 无论怎么用，其真正使用的 个数都会小于single_Max_Num
。 所以可以对这种类型的物品进行完全背包的类型处理。 当然这种类型也可以转换成01背包处理。这将是这个题目的另一种解法，见解法二！*/ if(single_V*single_Max_Num>g_All_V)// { ComepletePack(
single_Value, single_V ); print(); return ; } //***************************************************************************************************************** /*否则就是如下，将多重背包转换成01背包，从而用来求解 (1) 题目 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件体积是c[i]，价值是w[i]。 求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。 (2)基本算法 这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可， 因为对于第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]} 复杂度是O(V*Σn[i])。 (3)解题思想 用以下方法转化为普通01背包问题：将第i种物品（将本物品看成物品大类）分成若干物品小类， 其中每件物品小类有一个系数（假设为x）， 这件物品小类的体积和价值均是原来的体积和价值乘以这个系数x， 这样我们实际上是对这些物品小类 进行01背包处理， 且这些物品小类的体积和价值 是对应的 单个物品大类的 体积和价值 x倍。 具体的x值如下解析： 使这些系数分别为 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的四件物品小类。 这种方法能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示。 这个很容易证明，证明过程中用到以下定理： 任何一个整数n均可以表示成：n=a0*2^0+a1*2^1+…+ak*2^k,其中ak=0或者1(实际上就是n的二进制分解)， 定理：一个正整数n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是满足n-2^k+1>0的最大整数）的形式， 且1～n之内的所有整数均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某几个数的和的形式。 (4)该定理的证明如下： （1） 数列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和为n，所以若干元素的和的范围为：[1, n]； （2） 如果正整数t<=
2^k - 1,则t一定能用1,2,4,…,2^(k-1)中某几个数的和表示，这个很容易证明： 我们把t的二进制表示写出来，很明显，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1）， 其中ak=0或者1，表示t的第ak位二进制数为0或者1. （3） 如果t>=2^k,设s=n-2^k+1，则t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某几个数的和的形式， 进而t可以表示成1,2,4,…,2^(k-1)，s，，中某几个数的和（加数中一定含有s）的形式。 （证毕！） 该算法的时间复杂度为：O(V*sum(logn[i])). (5)实例解析 把这种类型的的物品分成几种不同的类型， 如：对体积为2，价值为100，数量为4的这种类型，可以分成 single_Max_Num表示 此物品小类可以使用的个数 1）当k = 1时，
Max_Num=4 2^(k-1)=2^(1-1)=2^0=1,
//n[i]-2^k+1=Max_Num-(2^k-1)=4-(2^1
- 1)=4 -1 = 3; single_Max_Num
= Max_Num - k = 4 - 1 = 3; 那么第一个物品小类的体积和价值表示：（2*1，100*1）； 2） 然后 k = 2 *
k = 2*1=2 < (single_Max_Num=3) 2^(k-1)=2^(2-1)=2^1=2,
//n[i]-2^k+1=Max_Num-(2^k-1)=4-(2^2
- 1)=4 -3 = 1; single_Max_Num
= single_Max_Num - k = 3 - 2 = 1; 那么第二个物品小类的体积和价值表示：（2*2，100*2）； 3） 然后 k = 2 *
2 = 2*2=4 > (single_Max_Num=1) 也就是说 物品小类的系数 是 2的整数倍的部分已经 处理完毕， 需要单独处理 一下 物品小类的系数 不是 2的整数倍的那一部分， 即
n[i]-2^k+1=Max_Num-(2^k-1)=4-(2^2 - 1)=4 -3 = 1; 那么第三个物品小类的体积和价值表示：（2*1，100*1）； 三个小类组合 来表示体积为2，价值为100，数量为4的这种类型， 也就是相当与把这种类型拆分成了这三种类型每种类型的数量均为一（就转换成了01背包问题）， 然后对这三种类型单一处理。 */ int k=1; while( k<=single_Max_Num ) //物品小类的系数 是 2的整数倍的部分 处理 { cout<<"2^k中的k="<<k<<",单个物品可用体积single_Max_Num=
"<<single_Max_Num<<endl; ZeroOnePack(
k*single_Value, k*single_V ); print(); single_Max_Num -= k; k = 2 * k; } ZeroOnePack( single_Max_Num*single_Value, single_Max_Num*single_V );//物品小类的系数 不是 2的整数倍的部分 处理 print(); cout<<"void
MultiplePack ( int single_Value, int single_V, int single_Max_Num ) end end end end end!!!"<<endl; } void print() { //
cout<<"一维数组的内容："<<endl; for (int i=0; i <=g_All_V; i++) { printf("%4d",i); } cout<<endl; for ( i=0; i <=g_All_V; i++) { printf("%4d",f[i]); } cout<<endl; } int main() { //all_kind:相当于物品种类，或者金矿数 int Case; int isingle_Value[MAX],iSingle_V[MAX],inum[MAX]; //
ifstream cin("b.txt"); freopen("a.txt","r",stdin); freopen("1_多重背包.txt","w",stdout); cin>>Case; int all_kind; //
while(Case--) // { int MM=-1; cin>>g_All_V>>all_kind; //
cout<<g_All_V<<" "<<all_kind; memset(f,0,sizeof(f)); // 要是背包不要求完全装满，都可以全部赋值为零。 for( int i=0; i<all_kind; i++ ) // 赋值 { cin>>iSingle_V[i]; cin>>isingle_Value[i]; cin>>inum[i]; } for( i=0; i<all_kind; i++ ) // { cout<<"第"<<i<<"个物品=>:
"<<"体积："<<setw(4)<<iSingle_V[i]<<"，价值："<<setw(4)<<isingle_Value[i]<<"，可用个数："<<setw(4)<<inum[i]<<endl; } cout<<endl<<endl; cout<<"开始多重背包@&&"<<endl; for(i=0; i<all_kind; i++ ) { cout<<endl<<endl<<"第"<<i<<"轮多重背包=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>=>"<<endl; MultiplePack(
isingle_Value[i], iSingle_V[i], inum[i] ); // 可见是个多重背包问题所以用多重背包的算法。 cout<<"第"<<i<<"轮多重背包结果=>=>=>=>=>"<<endl; print(); } cout<<endl<<"结束多重背包!!!!!!!!!!!!!!!!!!!"<<endl; for(i=0; i<=g_All_V; i++ ) //找出最大值 if(f[i]>MM) MM=f[i]; cout<<endl<<"找出最大值: "<<MM<<endl; //
system("pause"); // } return 0; }
//#include<iostream> a1.txt内容： 2 20 5 第0个物品=>: 体积： 17，价值： 92，可用个数： 1
结束多重背包!!!!!!!!!!!!!!!!!!! 找出最大值: 400 |
|
|
