0-1背包(動態(tài)規(guī)劃、回溯)和背包(貪心)實驗報告

《0-1背包(動態(tài)規(guī)劃、回溯)和背包(貪心)實驗報告》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

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

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

3、最優(yōu)值為m(i,j),即m(i,j)是背包容量為j,可選擇物品為i,i+1,…，n吋0?1背包問題的最優(yōu)值。由0?1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i,j)的遞歸式如下。m(i,7)=回溯法：在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結(jié)點是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。(2)背包問題貪心算法：首先計算每種物品單位重量的價值Vi/Wi,然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全

4、部裝入背包后，背包內(nèi)的物晶總重量未超過C,則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。一.測試數(shù)據(jù)及運行結(jié)果1.正常測試數(shù)據(jù)(3組)及運行結(jié)果0-1背包問題：動態(tài)規(guī)劃法：回溯法:**J:DebugZeroAndOneKnap$ack（回溯）?exe"請輸入背包最大重量：10請輸入可選物品O：5輸入第1號物品的重量和價值:26輸入第2號物品的重量和價值:23輸入第3號物品的重量和價值:65輸入第4號物品的重量和價值:54輸入第5號物品的重量和價值:46排序后的物品內(nèi)容如下:背包最大能裝的重量為：10.00第1號物品重:2.00/

5、第2號物品重:2.00/第3號物品重：4.00/第4號物品重：6.00/第5號物品重:5.00/ooooOooooO???654值值值值值介介介介介??J:DebugZeroAndOneKnapsack（回溯）?exe”65輸入第4號物品的重量和價值：54輸入第5號物品的重量和價值：46排序后的物品內(nèi)容如下：背包最大能裝的重量為：10.00第1號物品重：2.00,1第2號物品重：2.00,1第3號物品重：4.00,1第4號物品重：6.00,1笫5號物品重：5.00,1介值:介值:介值:介值:介值:6.003.006.005.004.00所有物品總垂量為：19.00,總價值為

6、：24.00可將以下物品裝入背包,使背包裝的物品價值最大:第1號物品，畫量：2.00,價值：6.00第3號物品，重量：4.00,價值：6.00背包中物品最大重量為：6.00,最大價值為：15.00Pressanykeytoconiinue背包問題:貪心算法:■J'Debug'KnapsacIc（貪心）?exe*10請輸入物品個數(shù)：5請輸入第1個物品的重園及價值:26請輸入第2個物品的重量及價值:23請輸入第3個物品的重量及價值:65請輸入第4個物品的重量及價值:54請輸入第5個物品的更量及價值:46Weight:2.00Weight:2.00Weight:4.00Weight:

7、2.00ResuIt:1,2,5,3,Number：bkjmber：Number：bkimber：SumValue：16.67Pressanykeytocontinue一.調(diào)試情況，設(shè)計技巧及體會木次的實驗大體理解和掌握0?1背包（動態(tài)規(guī)劃算法、回溯算法）和背包（貪心算法）的問題描述、算法設(shè)計思想、程序設(shè)計、算法復(fù)雜性分析、他們的區(qū)別及聯(lián)系。通過本次上機實驗，我對0?1背包（動態(tài)規(guī)劃算法、回溯算法）和背包（貪心算法）有了更為深刻的了解，利用動態(tài)規(guī)劃算法、回溯算法和貪心可以將問題簡化,這有助于