背包（動態(tài)規(guī)劃回溯）和背包（貪心）實驗報告.doc

《背包（動態(tài)規(guī)劃回溯）和背包（貪心）實驗報告.doc》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、西安郵電學院算法設計與分析課內(nèi)試驗報告題目：0-1背包(動態(tài)規(guī)劃、回溯)和背包(貪心)院系名稱：計算機學院專業(yè)名稱：軟件工程專業(yè)班級：0903班學生姓名：張橋?qū)W號（8位）：(23)指導教師：陳琳時間：2011年12月一.設計目的通過上機實驗：深刻理解和掌握0-1背包(動態(tài)規(guī)劃算法、回溯算法)和背包(貪心算法)的問題描述、算法設計思想、程序設計、算法復雜性分析、他們的區(qū)別及聯(lián)系。二.設計內(nèi)容1問題的描述(1)0-1背包問題給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為c。問應如何選擇裝入背包中的物品，使得裝入背包中物

2、品的總價值最大？(2)背包問題與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1<=i<=n。2算法設計思想(1)0-1背包問題動態(tài)規(guī)劃法：是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。由于動態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個特點，為減少重復計算，對每一個子問題只解一

3、次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中。設所給0-1背包問題的子問題的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構性質(zhì)，可以建立計算m(i，j)的遞歸式如下。回溯法：在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。(1)背包問題貪心算法：首先計算每種物品

4、單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。三．測試數(shù)據(jù)及運行結(jié)果1．正常測試數(shù)據(jù)（3組）及運行結(jié)果0-1背包問題：動態(tài)規(guī)劃法：回溯法：背包問題：貪心算法：四．調(diào)試情況，設計技巧及體會本次的實驗大體理解和掌握0-1背包(動態(tài)規(guī)劃算法、回溯算法)和背包(貪心算法)的問題描述、算法設計思想、程序設計、算法復雜性分析、他們的區(qū)別及聯(lián)系。通過本次上機實

5、驗，我對0-1背包(動態(tài)規(guī)劃算法、回溯算法)和背包(貪心算法)有了更為深刻的了解，利用動態(tài)規(guī)劃算法、回溯算法和貪心可以將問題簡化，這有助于我們在實際問題中解決一些復雜性較大的問題，提高程序的運行效率。但要注意他們的區(qū)別與不同的應用場景。五.源代碼1）0-1背包：動態(tài)規(guī)劃法：#include#defineMAX20voidKnapsack(int*value,int*weight,intcolumn,intlength,int(*middle)[MAX]);voidTraceBack(int(*middle)[MAX],

6、int*weight,intcolumn,intlength,int*x);intMax(intx,inty);intMin(intx,inty);intMin(intx,inty){returnx<=y?x:y;}intMax(intx,inty){returnx>=y?x:y;}voidTraceBack(int(*middle)[MAX],int*weight,intcolumn,intlength,int*x){inti;for(i=1;i

7、[column])x[i]=0;else{x[i]=1;column-=weight[i];}x[length]=(middle[length][column]?1:0);}voidKnapsack(int*value,int*weight,intcolumn,intlength,int(*middle)[MAX]){inti,j,jMax=Min(weight[length]-1,column);for(j=0;j<=jMax;j++)middle[length][j]=0;for(j=weight[length];j<=column

8、;j++)middle[length][j]=value[length];for(i=length-1;i>1;i--){jMax=Min(weight[i]-1,column);for(j=0;j<=jM