求解背包問題

1、一.題目求解背包問題，給出動態(tài)規(guī)劃算法，并完成以下要求：a、對于下邊背包問題的實例，應(yīng)用自底向上動態(tài)規(guī)劃算法求解。物品重量價值13252220311544405550已知：背包承重W=6b、a中的實例有多少個不同的最優(yōu)子集？c、一般來說，如何從動態(tài)規(guī)劃算法所生成的表中判斷出背包問題的實例是不是具有不 止一個最優(yōu)子集？二.解題思路(主要難點或關(guān)鍵點)階段劃分用動態(tài)規(guī)劃算法解決問題，首先是要找到解決問題的階段。設(shè)第k件物品的重量為wi,背包的總?cè)萘繛閙，在不考慮其他物品情況下:若當(dāng)前背包容量為0 wi-1，則一定不能選取第i件物品；若當(dāng)前背包容量為wim，就有可能選取第i件物品。結(jié)構(gòu)設(shè)計設(shè)一個存儲

2、動態(tài)規(guī)劃過程的二維數(shù)組cim共有0n行，0m列。行下表代表 0n件物品，列下標(biāo)代表當(dāng)前背包容量。元素中存儲的是當(dāng)前階段可能的最大獲利值。狀態(tài)轉(zhuǎn)移解決過程從第n件物品開始，j代表當(dāng)前背包容量：cij=0，j=0,1,2, ,，wi-1cij= pn，j= wi，wi+1，wi+2, ，m現(xiàn)在開始第二階段，解決第n-1件物品的取舍可能，及當(dāng)前的獲利情況。分下面 幾種情況進行討論。當(dāng)前背包容量jwi-1時，可以選取第i-1件物品，也可以不選第i-1件物品。若選取第i-1件物品，則對于其前面階段物品的獲利值，就只能考慮容量為 j-wi-1的情況，這時： TOC o 1-5 h z ci-1j= cij

3、- wi-1+ pi-1，j= wi-1，wi-1+1，m若不選取第i-1件物品，則獲利與上一階段相同：ci-1j= cij，j= wi-1，wi-1+1，m要獲取最大獲利，自然要取這兩種獲利中最大的一個，即：ci-1j=maxcij-wi-1+pi-1，cij，(j=wi-1，wi-1+1，m)以上每個階段都和第二階段一樣，由上一階段的可能獲利情況，遞推出本階 段的結(jié)論.301520354045604015203540(2)5560(2)50152035405565四.算法效率分析(時間、空間)岸時間效率O (n*m)r=五，實驗過程算法具體實現(xiàn)#includeintc67;intknapsack(int m,int n)int i,j,w5,p5;for(i=1;i=n;i+)scanf(n%d,%d”,&wi,&pi);for(i=0;i6;i+)for(j=0;j7;j+)cij=0;for(i=1;i=n;i+)for(j=1;j=m;j+)if(wici-1j)cij=pi+ci-1j-wi;else cij=ci-1j;else cij=ci-1j;return(cnm);int main()int m,n;int i,j;scanf(%d,%d”,&m,&n);printf(%d”,knapsack(m,n);printf(n);f