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

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

1、0/1背包問題動態(tài)規(guī)劃詳解及C代碼動態(tài)規(guī)劃是用空間換時間的一種方法的抽象。其關(guān)鍵是發(fā)現(xiàn)子問題和記錄其結(jié)果。然后利用這些結(jié)果減輕運(yùn)算量。比如01背包問題。/*一個旅行者有一個最多能用M公斤的背包，現(xiàn)在有N件物品，它們的重量分別是W1，W2，...,Wn,它們的價值分別為P1,P2,...,Pn.若每種物品只有一件求旅行者能獲得最大總價值。輸入格式：M,NW1,P1W2,P2......輸出格式：X*/因?yàn)楸嘲畲笕萘縈未知。所以，我們的程序要從1到M一個一個的試。比如，開始任選N件物品的一個?？磳?yīng)M的背包，能不能放進(jìn)去，如果能放進(jìn)去，并且還有

2、多的空間，則，多出來的空間里能放N-1物品中的最大價值。怎么能保證總選擇是最大價值呢？看下表。測試數(shù)據(jù)：10,33,44,55,6c[i][j]數(shù)組保存了1,2,3號物品依次選擇后的最大價值.這個最大價值是怎么得來的呢?從背包容量為0開始,1號物品先試,0,1,2,的容量都不能放.所以置0,背包容量為3則里面放4.這樣,這一排背包容量為4,5,6,....10的時候，最佳方案都是放4.假如1號物品放入背包.則再看2號物品.當(dāng)背包容量為3的時候，最佳方案還是上一排的最價方案c為4.而背包容量為5的時候，則最佳方案為自己的重量5.背包容量為7的時

3、候，很顯然是5加上一個值了。加誰??很顯然是7-4=3的時候.上一排c3的最佳方案是4.所以。總的最佳方案是5+4為9.這樣.一排一排推下去。最右下放的數(shù)據(jù)就是最大的價值了。(注意第3排的背包容量為7的時候,最佳方案不是本身的6.而是上一排的9.說明這時候3號物品沒有被選.選的是1,2號物品.所以得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)境下通過）:#includein

4、tc[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++)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]

5、[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]);}intmain(){intm,n;inti,j;printf("請輸入背包的承重量,物品的總個數(shù)：");scanf("%d,%d",&m,&n);printf("旅行者背包能裝的最大總價值為%d",knapsack

6、(m,n));printf("");return0;}