首頁  >  文章  >  web前端  >  JS教學--動態規劃演算法背包容量問題

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

php是最好的语言
php是最好的语言原創
2018-08-09 16:37:541812瀏覽

背包問題

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

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

#我們每次從左至右,保存前一次的資料
從上到下時,保存前一行的數據
所以我們總的來說只用保存一行的數據,空間複雜度為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中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn