蠻力法、動態(tài)規(guī)劃法、回溯法和分支限界法求解01背包問題

1、蠻力法、動態(tài)規(guī)劃法、溯法和分支限界法求解01背包問題一、實驗內容：分別用蠻力法、動態(tài)規(guī)劃法、回溯法和分支限界法求解0/1背包 問題。注：0/1背包問題：給定n種物品和一個容量為C的背包，物品 i的重量是wi，其價值為vi，背包問題是如何使選擇裝入背包內的物品， 使得裝入背包中的物品的總價值最大。其中，每種物品只有全部裝入背包或 不裝入背包兩種選擇。二、所用算法的基本思想及復雜度分析：蠻力法求解0/1背包問題：1）基本思想：對于有n種可選物品的0/1背包問題，其解空間由長度為n的0-1向量組成，可用子集數表示。在搜索解空間樹時，深度優(yōu)先遍歷， 搜索每一個結點，無論是否可能產生最優(yōu)解，都遍歷至葉子

2、結點，記錄 每次得到的裝入總價值，然后記錄遍歷過的最大價值。2）代碼：#includeiostream#includealgorithmusing namespace std;#define N 100 /最多可能物體數struct goods 物品結構體(int sign; 物品序號int w; 物品重量int p; /物品價值)aN；bool m(goods a,goods b)(return (a.p/a.w)(b.p/b.w);)int max(int a,int b)(return ab?b:a;)int n,C,bestP=0,cp=0,cw=0;int XN,cxN;/*蠻力法求

3、解0/1背包問題*/int Force(int i)(if(in-1)(if(bestPcpcw+ai.w=C)for (int k=0;kk+) Xk=cxk;/ 存儲最優(yōu)路徑 bestP二cp;)return bestP;)cw=cw+ai.w;cp=cp+ai.p;cxi=1; 裝入背包Force(i + 1);cw=cw-ai.w;cp=cp-ai.p;cxi=0; /不裝入背包Force(i + 1);return bestP;)int KnapSack1(int n,goods a,int C,int x)(Force(0);return bestP;)int main()(goo

4、ds bN;printf(物品種數 n:);scanf(%d, 輸入物品種數printf(背包容量 C:);scanf(%d, /輸入背包容量for (int i=0;ii +) 輸入物品i的重量w及其價值v(printf(-物品%d的重量w%d及其價值v%d:,i+1,i+1,i+1);scanf(%d%d,ai.w,ai.p);bi=ai;)int sum1=KnapSack1(n,a,C,X);/調用蠻力法求 0/1 背包問題 printf(蠻力法求解0/1背包問題:nX=);for(i=0;ii + +)coutXi ;/輸出所求Xn矩陣printf(裝入總價值%dn,sum1);be

5、stP=0,cp=0,cw=0;/ 恢復初始化)復雜度分析：蠻力法求解0/1背包問題的時間復雜度為：T(n) O(2n)。動態(tài)規(guī)劃法求解0/1背包問題：基本思想：令V(i,j)表示在前i(1 i n)個物品中能夠裝入容量為j(1 j C)的背包中的物品的最大值，則可以得到如下動態(tài)函數：V(i,0) V(0,j) 0V(i 1,j)(j wi) V(i,j) V(i 1,j),V(i 1,j wi) vi (j wi) max按照下述方法來劃分階段：第一階段，只裝入前1個物品，確定 在各種情況下的背包能夠得到的最大價值；第二階段，只裝入前2 個物品，確定在各種情況下的背包能夠得到的最大價值；以此

6、類推，直到 第n個階段。最后，V(n,C)便是在容量為C的背包中裝入n個物品時取 得的最大價值。代碼：#includeiostream#includealgorithmusing namespace std;#define N 100 /最多可能物體數struct goods( 物品結構體int sign; /物品序號int w; /物品重量int p; 物品價值)aN；bool m(goods a,goods b)(return (a.p/a.w)(b.p/b.w);)int max(int a,int b)(return ab?b:a;)int n,C,bestP=0,cp=0,cw=0;

7、int XN,cxN;int KnapSack2(int n,goods a,int C,int x)(int VN10*N; for(int i=0;ii + +) Vi=0; for(int j=0;jj +) Vj=0; for(i = 1;ii + +) for(j = 1;jj +) 初始化第0列初始化第0行計算第i 行，進行第i次迭代if(jai-1.w) Vij=Vi-1j; else Vij = max(Vi-1j,Vi-1j-ai- 1.w+ai-1.p); j=C; 求裝入背包的物品 for (i=n;ii-) ( if (VijVi- 1j)( xi-1 = 1; j=j

8、-ai-1.w; xi-1=0; else return VnC; /返回背包 取得的最大價值int main()(goods bN;printf(物品種數 n: ”)；scanf(%d, 輸入物品種數 printf(背包容量 C: ); scanf(%d, / 輸入背包容量for (int i=0;ii +) /輸入物品i的重量w及其價值v ( printf(-物品 %d 的重量 w%d及其價值 v%d: ,i+1,i+1,i+1); scanf(%d%d,ai.w,ai.p); bi=ai;)int sum2=KnapSack2(n,a,C,X);/調用動態(tài)規(guī)劃法求0/1背包問題 prin

9、tf(-動態(tài)規(guī)劃法求解0/1背包問題:nX=);for(i=0;ii + +) coutXi ;/輸出所求 Xn矩陣 printf(裝入總價 值%dn,sum2); for (i=0;ii +) ( ai = bi; /恢復 aN順序)3)復雜度分析：動態(tài)規(guī)劃法求解0/1背包問題的時間復雜度為：T(n) O(n C)?；厮莘ㄇ蠼?/1背包問題：1)基本思想：回溯法：為了避免生成那些不可能產生最佳解的問題狀態(tài)，要不 斷地利用限界函數(bounding function)來處死那些實際上不可能產 生所需解的活結點，以減少問題的計算量。這種具有限界函數的深度 優(yōu)先生成法稱為回溯法。對于有n種可選物品

10、的0/1背包問題，其解空間由長度為n的 0-1向量組成，可用子集數表示。在搜索解空間樹時，只要其左兒子結 點是一個可行結點，搜索就進入左子樹。當右子樹中有可能包含最優(yōu)解 時就進入右子樹搜索。2)代碼：#includeiostream#includealgorithmusing namespace std;#define N 100 /最多可能物體數struct goods 物品結構體(int sign; 物品序號int w; 物品重量int p; 物品價值)aN;bool m(goods a,goods b)(return (a.p/a.w)(b.p/b.w);)int max(int a,i

11、nt b)(return ab?b:a;)int n,C,bestP=0,cp=0,cw=0;int XN,cxN;int BackTrack(int i)(if(in-1)( if(bestPcp)( for (int k=0;kk+) bestP=cp; Xk=cxk;/ 存 儲最優(yōu)路徑 return bestP; /進入左子樹 if(cw+ai.w=C)( cw=cw+ai.w; cp=cp+ai.p; cxai.sign=1; / 裝入背 包 BackTrack(i + 1); cw=cw-ai.w; cp=cp-ai.p; 回溯，進入右子樹cxai.sign=0; 不裝入背包Back

12、Track(i+1);return bestP;int KnapSack3(int n,goods a,int C,int x)(for(int i=0;ii +) ( xi=0; ai.sign = i; sort(a,a + n,m);/ 將各物品按 單位重量價值降序排列BackTrack(0);return bestP;int main()(goods bN;printf(物品種數n: ); scanf(%d, /輸入物品種數printf(背包容 量 C: ); scanf(%d, / 輸入背包容量 for (int i=0;ii +) / 輸入物品 i 的 重量w及其價值v print

13、f(-物品%d的重量w%d及其價值v%d: ,i+1,i+1,i+1); scanf(%d%d,ai.w,ai.p);bi=ai;int sum3=KnapSack3(n,a,C,X);/調用回溯法求 0/1 背包問題printf(回溯法求解 0/1 背包問題:nX= ); for(i=0;ii + +) coutXi ;/輸出所求 Xn矩陣 printf(裝入總價值%dn,sum3); for (i=0;ii + +) ai=bi; 恢復 aN順序復雜度分析：最不理想的情況下，回溯法求解0/1背包問題的時間復雜度為:T(n) O(2n)。由于其對蠻力法進行優(yōu)化后的算法，其復雜度一般比 蠻力法

14、要小?？臻g復雜度：有n個物品，即最多遞歸n層，存儲物品信息就是 一個一維數組，即回溯法求解0/1背包問題的空間復雜度為O(n)。分支限界法求解背包問題：1)基本思想：分支限界法類似于回溯法，也是在問題的解空間上搜索問題解的 算法。一般情況下，分支限界法與回溯法的求解目標不同?；厮莘?的求解目標是找出解空間中滿足約束條件的所有解，而分支限界法的求 解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找 出使某一目標函數值達到極大或極小的解，即在某種意義下的最優(yōu)解。首先，要對輸入數據進行預處理，將各物品依其單位重量價值從 大到小進行排列。在下面描述的優(yōu)先隊列分支限界法中，節(jié)點的優(yōu)先級由已裝

15、袋的 物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價 值和。算法首先檢查當前擴展結點的左兒子結點的可行性。如果該左兒 子結點是可行結點，則將它加入到子集樹和活結點優(yōu)先隊列中。當 前擴展結點的右兒子結點一定是可行結點，僅當右兒子結點滿足上界約 束時才將它加入子集樹和活結點優(yōu)先隊列。當擴展到葉節(jié)點時為問題的 最優(yōu)值。2）代碼：#includeiostream#includealgorithmusing namespace std;#define N 100 /最多可能物體數struct goods 物品結構體(int sign; 物品序號int w; 物品重量int p; /物品價值)a

16、N；bool m(goods a,goods b)(return (a.p/a.w)(b.p/b.w);)int max(int a,int b)(return ab?b:a;)int n,C,bestP=0,cp=0,cw=0;int XN,cxN;struct *E /狀態(tài)結構體(bool s1N; 當前放入物體int k; 搜索深度int b; 價值上界int w; /物體重量int p; /物體價值;struct HEAP /堆元素結構體(*E *p;/結點數據int b; 所指結點的上界;交換兩個堆元素void swap(HEAP a, HEAP b)(HEAP temp = a;a

17、 = b;b = temp;)堆中元素上移void mov_up(HEAP H, int i)(bool done = false;if(i! = 1)while(!done i! = 1)if(Hi.bHi/2.b)swap(Hi, Hi/2);)elsedone = true;)i = i/2;)堆中元素下移void mov_down(HEAP H, int n, int i)bool done = false;if(2*i)=n)while(!done (i = 2*i) = n)if(i + 1=n Hi + 1.b Hi.b)i+；)if(Hi/2.bHi.b)(swap(Hi/2,

18、 Hi);)else(done = true;)往堆中插入結點void insert(HEAP H, HEAP x, int n) ( n + + ;Hn = x;mov_up(H,n);)刪除堆中結點void del(HEAP H, int n, int i)(HEAP x, y;x = Hi; y = Hn;n -；if(i = n)(Hi = y;if(y.b=x.b)(mov_up(H,i);)else(mov_down(H, n, i);)獲得堆頂元素并刪除HEAP del_top(HEAP H, int n)(HEAP x = H;del(H, n, 1);return x;)計算

19、分支節(jié)點的上界void bound( *E* node, int M, goods a, int n)(int i = nodefloat w = nodefloat p = node-if(node-wM)( /物體重量超過背包載重量node-b = 0; /上界置為0)else(while(w+ai.w=M)(in)(w += ai.w; /計算背包已裝入載重p += ai + +.p; /計算背包已裝入價值)if(in)(node-b = p + (M - w)*ai.p/ai.w;)else(node - b = p;)用分支限界法實現0/1背包問題int KnapSack4(int

20、n,goods a,int C, int X)(int i, k = 0; /堆中元素個數的計數器初始化為0int v;*E *xnode, *ynode, *znode;HEAP x, y, z, *heap;heap = new HEAPn*n; /分配堆的存儲空間for( i=0; i i +)(ai.sign=i; /記錄物體的初始編號)sort(a,a + n,m); /對物體按照價值重量比排序 xnode = new *E; / 建立父親結點 for( i=0; i i +)( / 初始化結點xnode-s1i = false;)xnode-k = xnode-w = xnode-

21、p = 0;while(xnode-kn) (ynode = new *E; / 建立結點 y*ynode = *xnode; /結點x的數據復制到結點y ynode-s1ynode-k = true; / 裝入第 k 個物體 ynode-w += aynode-k.w; /背包中物體重量累計 ynode-p += aynode-k.p; /背包中物體價值累計 ynode-k + + ; / 搜索深度+ +bound(ynode, C, a, n); / 計算結點 y 的上界 y.b = ynode-y.p = ynode;insert(heap, y, k); /結點y按上界的值插入堆中zn

22、ode = new *E; / 建立結點 z*znode = *xnode; /結點x的數據復制到結點z znode- /搜索深度+ +bound(znode, C, a, n); 計算節(jié)點z的上界z.b = znode-z.p = znode;insert(heap,乙k); /結點z按上界的值插入堆中 delete xnode;x = del_top(heap, k); 獲得堆頂元素作為新的父親結點 xnode = x.p;)v = xnode-for( i=0; i i +)( /取裝入背包中物體在排序前的序號 if(xnode-s1i)(Xai.sign =1 ;)else(Xai.sign = 0;)delete xnode;delete heap;return v;