算法設計與分析 課件 5.4.3-動態規劃-0-1背包問題-空間優化_第1頁
算法設計與分析 課件 5.4.3-動態規劃-0-1背包問題-空間優化_第2頁
算法設計與分析 課件 5.4.3-動態規劃-0-1背包問題-空間優化_第3頁
算法設計與分析 課件 5.4.3-動態規劃-0-1背包問題-空間優化_第4頁
算法設計與分析 課件 5.4.3-動態規劃-0-1背包問題-空間優化_第5頁
已閱讀5頁，還剩8頁未讀， 繼續免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

信息工程大學算法設計與分析動態規劃—0-1背包問題之優化和拓展國家級實驗教學示范中心計算機學科組規劃教材算法設計與分析Python案例詳解微課視頻版

動態規劃求解0-1背包問題時，空間復雜度為O(nc)。如果物品數n和背包容量c非常大時，算法對空間的需求也很大。

f(i,j)=max{vi

+f(i+1,j-wi),f(i+1,j)}000000000000000:n1w-wici0i+1w思考：是否可以對空間優化？000:1w-wicf[0]f[1]w00f[0]f[1]以f[1]為基礎計算f[0]f[0]復制到f[1]中空間從f[n+1][c+1]

降低為f[2][c+1]。滾動數組f[k][j]=max{vi

+f[1-k][

j-wi],f[1-k][j]}k輪流取0,1000:1w-wicf[0]f[1]w空間從f[n+1][c+1]

降低為f[2][c+1]。進一步，是否可以使用一維數組？00000000000d0ab00分析依賴關系，自右向左計算f[j]=max{vi

+f[j-wi],f[j]}單選題。如果使用一維數組的話，可以按照自左向右的順序計算0-1背包問題嗎？A.可以B.不可以單選題。對0-1背包問題進行空間優化后，還可以利用f數組求解最優解嗎？A.能B.不能0-1背包代表了一類問題，具有以下特征：已知：n個可選擇的物品每個物品有若干屬性，比如重量和價值一個容器（背包），有一個屬性上的限制（容量）問題：在容器限制下，如何挑選物品（每個物品要么選要么不選）才能使得另一個屬性達到極大值？書名價格評級ACM知識與入門351算法競賽入門到進階592ACM競賽題解793ACM算法基礎訓練教程552ACM基本算法393算法競賽三部曲2402ACM高級教程1994挑戰程序設計競賽1633算法競賽寶典1325某同學為參加程序設計競賽準備購買一批書籍，預算只有500元，他為不同書籍的重要性進行了評級：1~5。問題：在預算有限的情況下，如何選擇才能使所買的所有書籍總的重要性最高？預算即背包容量書籍的價格即物品的重量書籍的重要性物品的價值集裝箱裝載特種兵背包物品的選擇滿背包問題選擇哪些物品剛好可以裝滿背包且價值最大完全背包問題每種物品有無限件多重背包問題第i種物品最多有Mi

件可用……理解和掌握典型應用的主要特征，這樣才能在不同的應用場景中，從現象到本質，抓住關鍵點，活學活用。1.如果背包容量c和物品重量wi是小數，是否可以用動態規劃求解0-1背包問題？2.若c>2n，則動態規劃的時間復雜度為Ω(n2n)。與窮舉法相比如何？3.0-1

溫馨提示

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

評論

0/150

提交評論