實(shí)驗(yàn)十一-0-1背包問題的設(shè)計(jì)與實(shí)現(xiàn)

實(shí)驗(yàn)十一0-1背包問題的設(shè)計(jì)與實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?．掌握動(dòng)態(tài)規(guī)劃算法的根本原理與方法2．利用動(dòng)態(tài)規(guī)劃方法編程解決0-1背包問題二、實(shí)驗(yàn)要求1．設(shè)計(jì)算法2．寫出相應(yīng)程序3．保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。三、實(shí)驗(yàn)內(nèi)容問題描述：給定n種物品和一個(gè)背包，物品i的重量是wi，其價(jià)值為vi，背包容量為C。在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有兩種選擇：裝入背包或不裝入背包，即不能將物品i裝入背包屢次，也不能只裝入物品i的一局部。問：如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大？在0/1背包問題中，物品i或者被裝入背包，或者不被裝入背包，設(shè)xi表示物品i裝入背包的情況，那么當(dāng)xi=0時(shí)，表示物品i沒有被裝入背包，xi=1時(shí)，表示物品i被裝入背包。根據(jù)問題的要求，有如下約束條件和目標(biāo)函數(shù)：〔〔1〕〔〔2〕令V(i,j)表示在前i(1≤i≤n)個(gè)物品中能夠裝入容量為j〔1≤j≤C〕的背包中的物品的最大值，那么可以得到如下動(dòng)態(tài)規(guī)劃函數(shù)：V(i,0)=V(0,j)=0實(shí)例：有5個(gè)物品，其重量分別是{2,2,6,5,4}，價(jià)值分別為{6,3,5,4,6}，背包的容量為10。根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè)(n+1)×(C+1)的二維表V，V[i][j]表示把前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值。按下述方法來(lái)劃分階段：第一階段，只裝入前1個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；依此類推，直到第n個(gè)階段。最后，V(n,C)便是在容量為C的背包中裝入n個(gè)物品時(shí)取得的最大價(jià)值。為了確定裝入背包的具體物品，從V(n,C)的值向前推，如果V(n,C)>V(n-1,C)，說(shuō)明第n個(gè)物品被裝入背包，前n-1個(gè)物品被裝入容量為C-wn的背包中；否那么，第n個(gè)物品沒有被裝入背包，前n-1個(gè)物品被裝入容量為C的背包中。依此類推，直到確定第1個(gè)物品是否被裝入背包中為止。由此，得到如下函數(shù)：算法：設(shè)n個(gè)物品的重量存儲(chǔ)在數(shù)組w[n]中，價(jià)值存儲(chǔ)在數(shù)組v[n]中，背包容量為C，數(shù)組V[n+1][C+1]存放迭代結(jié)果，其中V[i][j]表示前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值，數(shù)組x[n]存儲(chǔ)裝入背包的物品，動(dòng)態(tài)規(guī)劃法求解0/1背包問題的算法如下：intKnapSack(intn,intw[],intv[]){for(i=0;i<=n;i++)//初始化第0列V[i][0]=0;for(j=0;j<=C;j++)//初始化第0行V[0][j]=0;for(i=1;i<=n;i++)//計(jì)算第i行，進(jìn)行第i次迭代for(j=1;j<=C;j++)if(j<w[i])V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);j=C;//求裝入背包的物品for(i=n;i>0;i--){if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}returnV[n][C];//返回背包取得的最大價(jià)值}四、程序代碼#include<stdio.h>#defineMAX100inta(intn,intw[],intv[]){ intV[MAX][MAX]; intx[n]; inti,j; for(i=0;i<n+1;i++) V[i][0]=0; for(j=0;j<11;j++) V[0][j]=0; for(i=1;i<n+1;i++) for(j=1;j<11;j++) if(j<w[i-1]) V[i][j]=V[i-1][j]; else V[i][j]=V[i-1][j]>(V[i-1][j-w[i-1]]+v[i-1])?V[i-1][j]:(V[i-1][j-w[i-1]]+v[i-1]);/* for(i=0;i<n+1;i++){ for(j=0;j<11;j++) printf("%d\t",V[i][j]); printf("\n"); }*/ j=10; for(i=n;i>0;i--) if(V[i][j]>V[i-1][j]) { x[i-1]=1;j=j-w[i-1]; } else x[i-1]=0; printf("最大價(jià)值的組合為：\n"); for(i=0;i<n;i++) if(x[i]==1) printf("%d\t%d\n",w[i],v[i]);