實驗報告：動態(tài)規(guī)劃-0-1背包問題_第1頁
實驗報告：動態(tài)規(guī)劃-0-1背包問題_第2頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、4/4XXXX大 學(xué) 計 算 機 學(xué) 院 實 驗 報 告計算機學(xué)院 XXX 級 XXX 專業(yè)XXX 班 指導(dǎo)教師 XXX學(xué)號XXX 姓名 XXX XX年 XXX月 XXX日 成績 課程名稱算法分析與設(shè)計實驗名稱動態(tài)規(guī)劃0-1背包問題實驗?zāi)康睦斫膺f歸算法的概念通過模仿0-1背包問題，了解算法的思想練習(xí)0-1背包問題算法 實驗儀器和器材電腦、jdk、eclipse實驗內(nèi)容、上機調(diào)試程序、程序運行結(jié)果實驗內(nèi)容、上機調(diào)試程序、程序運行結(jié)果實驗內(nèi)容、上機調(diào)試程序、程序運行結(jié)果實驗：0-1背包算法：給定N種物品，每種物品都有對應(yīng)的重量weight和價值value，一個容量為maxWeight的背包，問：應(yīng)

2、該如何選擇裝入背包的物品，使得裝入背包的物品的總價值最大。（面對每個物品，我們只有拿或者不拿兩種選擇，不能選擇裝入物品的某一部分，也不能把同一個物品裝入多次）代碼如下所示：public class KnapsackProblem /* param weight 物品重量* param value 物品價值* param maxweight 背包最大重量* return maxvalueij中，i表示的是前i個物品數(shù)量，j表示的是重量*/public static int knapsack(int weight,int value,int maxweight)int n = ;包問題的算法思想：

3、 將前i個物品放入容量為w的背包中的最大價值。有如下兩種情況：若當(dāng)前物品的重量小于當(dāng)前可放入的重量，便可考慮是否要將本件物品放入背包中或者將背包中的某些物品拿出來再將當(dāng)前物品放進去；放進去前需要比較（不放這個物品的價值）和（這個物品的價值放進去加上當(dāng)前能放的總重量減去當(dāng)前物品重量時取i-1個物品是的對應(yīng)重量時候的最高價值），如果超過之前的價值，可以直接放進去，反之不放。若當(dāng)前物品的重量大于當(dāng)前可放入的重量，則不放入背包問題利用動態(tài)規(guī)劃的思路可以這樣理解：階段是“物品的件數(shù)”，狀態(tài)就是“背包剩下的容量”，fi,v表示設(shè)從前i件物品中選擇放入容量為V的背包的最大價值。那么狀態(tài)轉(zhuǎn)移的方法為:fiv=maxfi-1v,fi-1v-wi+ci這個方程可以理解為：只考慮子問題“將前i個物品放入容量為v的背包中的最大價值”那么可以考慮不放入i，最大價值就

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論