JS教學--動態規劃演算法背包容量問題

背包問題

題目
給定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]

1. f(i,v) = 0  (i

2. f(i,v) = c[0]  (i==1, v>=p[0]);

3. f(i,v) = f(i-1,v)    (i>1, v

4. #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實作動態規劃背包演算法

JavaScript高階演算法動態規劃實例分析

以上是JS教學--動態規劃演算法背包容量問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！