0-1背包問題動態(tài)規(guī)劃詳解及代碼.doc

《0-1背包問題動態(tài)規(guī)劃詳解及代碼.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、0/1背包問題動態(tài)規(guī)劃詳解及C代碼動態(tài)規(guī)劃是用空間換時間的一種方法的抽象。其關(guān)鍵是發(fā)現(xiàn)子問題和記錄其結(jié)果。然后利用這些結(jié)果減輕運(yùn)算量。問題描述：給定N中物品和一個背包。物品i的重量是Wi,其價值位Vi?，背包的容量為C。問應(yīng)該如何選擇裝入背包的物品，使得轉(zhuǎn)入背包的物品的總價值為最大？？在選擇物品的時候，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能講物品i裝入多次，也不能只裝入物品的一部分。因此，該問題被稱為0-1背包問題。??問題分析：令V(i,j)表示在前i(1<=i<=n)個物品中能夠裝入容量為就j(1<=j<=C)的背包中的物品的最大價值，則可以得到如

2、下的動態(tài)規(guī)劃函數(shù):(1)??V(i,0)=V(0,j)=0?(2)?V(i,j)=V(i-1,j)?jwi(1)式表明：如果第i個物品的重量大于背包的容量，則裝人前i個物品得到的最大價值和裝入前i-1個物品得到的最大價是相同的，即物品i不能裝入背包；第(2)個式子表明:如果第i個物品的重量小于背包的容量，則會有一下兩種情況：(a)如果把第i個物品裝入背包，則背包物品的價值等于第i-1個物品裝入容量位j-wi?的背包中的價值加上第i個物品的價值vi;?(b)如果第i個物品沒有裝入

3、背包，則背包中物品價值就等于把前i-1個物品裝入容量為j的背包中所取得的價值。顯然，取二者中價值最大的作為把前i個物品裝入容量為j的背包中的最優(yōu)解。比如01背包問題。因?yàn)楸嘲畲笕萘縈未知。所以，我們的程序要從1到M一個一個的試。比如，開始任選N件物品的一個?？磳?yīng)M的背包，能不能放進(jìn)去，如果能放進(jìn)去，并且還有多的空間，則，多出來的空間里能放N-1物品中的最大價值。怎么能保證總選擇是最大價值呢？看下表。測試數(shù)據(jù)：10,33,44,55,6c[i][j]數(shù)組保存了1,2,3號物品依次選擇后的最大價值.這個最大價值是怎么得來的呢?從背包容量為0開始,1號物品先試,0,1,

4、2,的容量都不能放.所以置0,背包容量為3則里面放4.這樣,這一排背包容量為4,5,6,....10的時候，最佳方案都是放4.假如1號物品放入背包.則再看2號物品.當(dāng)背包容量為3的時候，最佳方案還是上一排的最價方案c為4.而背包容量為5的時候，則最佳方案為自己的重量5.背包容量為7的時候，很顯然是5加上一個值了。加誰??很顯然是7-4=3的時候.上一排c3的最佳方案是4.所以?？偟淖罴逊桨甘?+4為9.這樣.一排一排推下去。最右下放的數(shù)據(jù)就是最大的價值了。(注意第3排的背包容量為7的時候,最佳方案不是本身的6.而是上一排的9.說明這時候3號物品沒有被選.選的是1,2號

5、物品.所以得9.)從以上最大價值的構(gòu)造過程中可以看出。f(n,m)=max{f(n-1,m),f(n-1,m-w[n])+P(n,m)}這就是書本上寫的動態(tài)規(guī)劃方程.這回清楚了嗎?下面是實(shí)際程序（在VC6.0環(huán)境下通過）:#includeintc[10][100];/*對應(yīng)每種情況的最大價值*/intknapsack(intm,intn){inti,j,w[10],p[10];printf("請輸入每個物品的重量,價值：");for(i=1;i<=n;i++)scanf("%d,%d",&w[i],&p[i]);for(i=0;i<10;i++)

6、for(j=0;j<100;j++)c[i][j]=0;/*初始化數(shù)組*/for(i=1;i<=n;i++)for(j=1;j<=m;j++){if(w[i]<=j)/*如果當(dāng)前物品的容量小于背包容量*/{if(p[i]+c[i-1][j-w[i]]>c[i-1][j])/*如果本物品的價值加上背包剩下的空間能放的物品的價值*//*大于上一次選擇的最佳方案則更新c[i][j]*/c[i][j]=p[i]+c[i-1][j-w[i]];elsec[i][j]=c[i-1][j];}elsec[i][j]=c[i-1][j];}return(c[n][m]);}intma

7、in(){intm,n;inti,j;printf("請輸入背包的承重量,物品的總個數(shù)：");scanf("%d,%d",&m,&n);printf("旅行者背包能裝的最大總價值為%d",knapsack(m,n));printf("");return0;}