算法設(shè)計(jì)與分析 課件 5.4.3-動態(tài)規(guī)劃-0-1背包問題-空間優(yōu)化

信息工程大學(xué)算法設(shè)計(jì)與分析動態(tài)規(guī)劃—0-1背包問題之優(yōu)化和拓展國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版

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

f(i,j)=max{vi

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

降低為f[2][c+1]。滾動數(shù)組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]。進(jìn)一步，是否可以使用一維數(shù)組？00000000000d0ab00分析依賴關(guān)系，自右向左計(jì)算f[j]=max{vi

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

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