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

2、的最大價值和裝入前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) jwi 輸入相應(yīng)的測試值，進行判斷程序的正確性；關(guān)鍵代碼int Knap(int n,int

3、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=0;i-)if(VijVi-1j)xi=1;j=j-wi;elsexi=0; printf(選中的物品是:n);for(i=0;in;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)，在進行實驗的過程最重要

4、的一步就是通過分析得到問題的動態(tài)規(guī)劃方程，因此就根據(jù)動態(tài)規(guī)劃方程來實現(xiàn)代碼。這個過程中最難的一步就是分析得到動態(tài)規(guī)劃方程，需要考慮各個可能的因素，最后再來用代碼實現(xiàn)。這次的實驗難度相比于前兩次實驗，明顯難多了，但是對于動態(tài)規(guī)劃算法的認識也頗多，理解也更加深刻了。實驗得分助教簽名附錄：完整代碼#include#includeint V200200;/前i個物品裝入容量為j的背包中獲得的最大價值int max(int a,int b) /一個大小比較函數(shù)，用于當總重大于第I行時 if(a=b) return a; else return b;int Knap(int n,int w,int v,i

5、nt 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=0;i-)if(VijVi-1j)xi=1;j=j-wi;elsexi=0; printf(選中的物品是:n);for(i=0;in;i+)printf(%d ,xi);printf(n);return Vn-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;in;i+)scanf(%d,&wi);printf(請分別輸入物品的價值:n);for(i=0;in;i+)scanf(%d,&