動態(tài)規(guī)劃法求解背包問題(共8頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法分析與設(shè)計實驗報告第 3次實驗姓名楊玉茹學(xué)號5班級計科1503時間3.31下午地點軟件大樓330 實驗名稱動態(tài)規(guī)劃法求解背包問題實驗?zāi)康耐ㄟ^上機(jī)實驗，要求掌握動態(tài)規(guī)劃算法的問題描述、算法設(shè)計思想、程序設(shè)計。實驗原理使用動態(tài)規(guī)劃算法的原理，即將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。分析出背包問題的動態(tài)規(guī)劃方程式，然后實現(xiàn)相應(yīng)的代碼，然后再進(jìn)行再輸入多組值進(jìn)行驗證，看輸出結(jié)果，然后來驗證自己的程序是否正確。實驗步驟 首先求出最優(yōu)子結(jié)構(gòu)，設(shè)（y1,y2,.,yn）是所給0-1背包問題的一個最優(yōu)解； 如果第i個物品的重量大于背包的

2、容量，則裝人前i個物品得到的最大價值和裝入前i-1個物品得到的最大價是相同的，即物品i不能裝入背包，得出方程為：  V(i,0)=V(0,j)=0如果第i個物品的重量小于背包的容量，則會有一下兩種情況：(a)如果把第i個物品裝入背包，則背包物品的價值等于第i-1個物品裝入容量位j-wi 的背包中的價值加上第i個物品的價值vi; (b)如果第i個物品沒有裝入背包，則背包中物品價值就等于把前i-1個物品裝入容量為j的背包中所取得的價值。顯然，取二者中價值最大的作為把前i個物品裝入容量為j的背包中的最優(yōu)解：  V(i,j)=V(i-1,j) 

3、0;j<wi    V(i,j)=maxV(i-1,j) ,V(i-1,j-wi)+vi) j>wi 輸入相應(yīng)的測試值，進(jìn)行判斷程序的正確性；關(guān)鍵代碼int Knap(int n,int w,int v,int x,int C)int i,j;for(i=0;i<=n;i+)Vi0=0;for(j=0;j<=C;j+)V0j=0;for(i=0;i<=n-1;i+)for(j=0;j<=C;j+)if(j<wi)Vij=Vi-1j;elseVij=max(Vi-1j,Vi-1j-wi+vi);j=C;for(i=n-1;i>=

4、0;i-)if(Vij>Vi-1j)xi=1;j=j-wi;elsexi=0; printf("選中的物品是:n");for(i=0;i<n;i+)printf("%d ",xi);printf("n");return Vn-1C;測試結(jié)果 實驗心得通過這次實驗，我回顧了0-1背包問題的動態(tài)規(guī)劃算法，因此更加深刻的了解到動態(tài)規(guī)劃算法的思想，由最優(yōu)子結(jié)構(gòu)來求解整個結(jié)構(gòu)的最優(yōu)結(jié)構(gòu)，在進(jìn)行實驗的過程最重要的一步就是通過分析得到問題的動態(tài)規(guī)劃方程，因此就根據(jù)動態(tài)規(guī)劃方程來實現(xiàn)代碼。這個過程中最難的一步就是分析得到動態(tài)規(guī)劃方程，需要

5、考慮各個可能的因素，最后再來用代碼實現(xiàn)。這次的實驗難度相比于前兩次實驗，明顯難多了，但是對于動態(tài)規(guī)劃算法的認(rèn)識也頗多，理解也更加深刻了。實驗得分助教簽名附錄：完整代碼#include<stdlib.h>#include<stdio.h>int V200200;/前i個物品裝入容量為j的背包中獲得的最大價值int max(int a,int b) /一個大小比較函數(shù)，用于當(dāng)總重大于第I行時 if(a>=b) return a; else return b;int Knap(int n,int w,int v,int x,int C)int i,j;for(i=0;i

6、<=n;i+)Vi0=0;for(j=0;j<=C;j+)V0j=0;for(i=0;i<=n-1;i+)for(j=0;j<=C;j+)if(j<wi)Vij=Vi-1j;elseVij=max(Vi-1j,Vi-1j-wi+vi);j=C;for(i=n-1;i>=0;i-)if(Vij>Vi-1j)xi=1;j=j-wi;elsexi=0; printf("選中的物品是:n");for(i=0;i<n;i+)printf("%d ",xi);printf("n");return V

7、n-1C;int main()int s;/獲得的最大價值int w4;/物品的重量 int v4;/物品的價值int x4;/物品的選取狀態(tài) 選中則是1 沒選中為0 int n,i;int C;/背包最大容量n=4;printf("請輸入背包的最大容量:n");scanf("%d",&C);printf("物品數(shù):n");scanf("%d",&n);printf("請分別輸入物品的重量:n");for(i=0;i<n;i+)scanf("%d",&wi);printf("請分別輸入物品的價值:n");for(i=0;i<n;i+)scanf("%d",&vi);s=Knap(n,w,v