（六）多重背包-- 二進制位壓縮解法--一維數(shù)組解析
//解法一：二進制位壓縮解法。 #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：相當(dāng)于 用于裝東西的 總體積，挖金礦總?cè)藬?shù)， //single_V：單個物品的體積 //single_Value：單個物品的價值 //single_Max_Num: 物品可用的最大個數(shù) 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; /* 當(dāng)
single_V*single_Max_Num>g_All_V, 理解為 當(dāng)對于某個種類的 單個物品的體積single_V
乘以 物品可用的最大個數(shù)
single_Max_Num ，大于 用于裝東西的 總體積g_All_V 也就是可以理解為對這種類型的物品可以無限的增加，因為對于本題來說 這個種類的物品個數(shù) 無論怎么用，其真正使用的 個數(shù)都會小于single_Max_Num
。 所以可以對這種類型的物品進行完全背包的類型處理。 當(dāng)然這種類型也可以轉(zhuǎn)換成01背包處理。這將是這個題目的另一種解法，見解法二！*/ if(single_V*single_Max_Num>g_All_V)// { ComepletePack(
single_Value, single_V ); print(); return ; } //***************************************************************************************************************** /*否則就是如下，將多重背包轉(zhuǎn)換成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的背包的最大權(quán)值，則有狀態(tài)轉(zhuǎn)移方程： f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]} 復(fù)雜度是O(V*Σn[i])。 (3)解題思想 用以下方法轉(zhuǎn)化為普通01背包問題：將第i種物品（將本物品看成物品大類）分成若干物品小類， 其中每件物品小類有一個系數(shù)（假設(shè)為x）， 這件物品小類的體積和價值均是原來的體積和價值乘以這個系數(shù)x， 這樣我們實際上是對這些物品小類 進行01背包處理， 且這些物品小類的體積和價值 是對應(yīng)的 單個物品大類的 體積和價值 x倍。 具體的x值如下解析： 使這些系數(shù)分別為 1,2,4,…,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數(shù)。 例如，如果n[i]為13，就將這種 物品分成系數(shù)分別為1,2,4,6的四件物品小類。 這種方法能保證對于0..n[i]間的每一個整數(shù)，均可以用若干個系數(shù)的和表示。 這個很容易證明，證明過程中用到以下定理： 任何一個整數(shù)n均可以表示成：n=a0*2^0+a1*2^1+…+ak*2^k,其中ak=0或者1(實際上就是n的二進制分解)， 定理：一個正整數(shù)n可以被分解成1,2,4,…,2^(k-1),n-2^k+1（k是滿足n-2^k+1>0的最大整數(shù)）的形式， 且1～n之內(nèi)的所有整數(shù)均可以唯一表示成1,2,4,…,2^(k-1),n-2^k+1中某幾個數(shù)的和的形式。 (4)該定理的證明如下： （1） 數(shù)列1,2,4,…,2^(k-1),n-2^k+1中所有元素的和為n，所以若干元素的和的范圍為：[1, n]； （2） 如果正整數(shù)t<=
2^k - 1,則t一定能用1,2,4,…,2^(k-1)中某幾個數(shù)的和表示，這個很容易證明： 我們把t的二進制表示寫出來，很明顯，t可以表示成n=a0*2^0+a1*2^1+…+ak*2^（k-1）， 其中ak=0或者1，表示t的第ak位二進制數(shù)為0或者1. （3） 如果t>=2^k,設(shè)s=n-2^k+1，則t-s<=2^k-1，因而t-s可以表示成1,2,4,…,2^(k-1)中某幾個數(shù)的和的形式， 進而t可以表示成1,2,4,…,2^(k-1)，s，，中某幾個數(shù)的和（加數(shù)中一定含有s）的形式。 （證畢！） 該算法的時間復(fù)雜度為：O(V*sum(logn[i])). (5)實例解析 把這種類型的的物品分成幾種不同的類型， 如：對體積為2，價值為100，數(shù)量為4的這種類型，可以分成 single_Max_Num表示 此物品小類可以使用的個數(shù) 1）當(dāng)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) 也就是說 物品小類的系數(shù) 是 2的整數(shù)倍的部分已經(jīng) 處理完畢， 需要單獨處理 一下 物品小類的系數(shù) 不是 2的整數(shù)倍的那一部分， 即
n[i]-2^k+1=Max_Num-(2^k-1)=4-(2^2 - 1)=4 -3 = 1; 那么第三個物品小類的體積和價值表示：（2*1，100*1）； 三個小類組合 來表示體積為2，價值為100，數(shù)量為4的這種類型， 也就是相當(dāng)與把這種類型拆分成了這三種類型每種類型的數(shù)量均為一（就轉(zhuǎn)換成了01背包問題）， 然后對這三種類型單一處理。 */ int k=1; while( k<=single_Max_Num ) //物品小類的系數(shù) 是 2的整數(shù)倍的部分 處理 { 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 );//物品小類的系數(shù) 不是 2的整數(shù)倍的部分 處理 print(); cout<<"void
MultiplePack ( int single_Value, int single_V, int single_Max_Num ) end end end end end!!!"<<endl; } void print() { //
cout<<"一維數(shù)組的內(nèi)容："<<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:相當(dāng)于物品種類，或者金礦數(shù) 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]<<"，可用個數(shù)："<<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<<"輪多重背包結(jié)果=>=>=>=>=>"<<endl; print(); } cout<<endl<<"結(jié)束多重背包!!!!!!!!!!!!!!!!!!!"<<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內(nèi)容： 2 20 5 第0個物品=>: 體積： 17，價值： 92，可用個數(shù)： 1
結(jié)束多重背包!!!!!!!!!!!!!!!!!!! 找出最大值: 400 |
|
|
