題目
給定N 種物品和一個容量為V 的背包,物品 i 的體積是wi,其價值為ci 。
(每種物品只有一個)
問:如何選擇裝入背包的物品,使得裝入背包中的物品的總價值最大?
面對每個物品,我們只有選擇放入或不放入兩個選擇,每種物品只能放入一次。
我們用之前同樣的思路來走一遍試試
假設只剩下最後一件物品,我們有兩種選擇
1.剩餘空間足夠時,選擇放入
2.剩餘空間不足時,不放入
所以我們有兩個最優的子結構:
1.容量為V的背包放入i-1件物品的最優選擇
2.容量為V-w[i]的背包放入i-1件物品的最優選擇
所以,綜合起來就是:
i件物品放入容量為V的背包的最優選擇:
max(容量為V的背包放入i-1件物品的最優選擇,容量為V-w[i]的背包放入i -1件物品的最優選擇c[i])
我們用f[i] [v]表示前i 件物品放入容量為v 的背包中可以獲得的最大價值。
用子問題定義狀態:
其狀態轉移方程式為:f[i] [v] = max{f[i-1] [v],f[i-1] [v-w[ i]] c[i]}。
我們先假設
背包總容量為V = 12
物品的容量數組為w = [4, 6, 2, 2, 5, 1]
價值數組為c = [8, 10, 6, 3, 7, 2]
f(i,v) = 0 (i
f(i,v) = c[0] (i==1, v>=p[0]);
f(i,v) = f(i-1,v) (i>1, v
#f(i,v) = max(f(i-1,v), f(i-1,v-w[i-1]) c[i-1])(i> 1, v>=w[i-1])
#我們每次從左至右,保存前一次的資料
從上到下時,保存前一行的數據
所以我們總的來說只用保存一行的數據,空間複雜度為O(V)
時間複雜度為O(N*V) ,空間複雜度為O(V);
但是,如果我們用原始的遞歸辦法去做,即排列組合的方法去做時
時間複雜度為O(2^N);
那麼當V很大,N較小時,例如V=1000,N=6時,用遞歸只用計算2^6=64次,而備受推崇的動態規劃就需要計算1000* 6=6000次
所以說,演算法沒有絕對的好壞,關鍵要看應用的慘景
相關推薦:
以上是JS教學--動態規劃演算法背包容量問題的詳細內容。更多資訊請關注PHP中文網其他相關文章!