背包問題

題目
給定 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<=1, v<w[0]);

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

3. f(i,v) = f(i-1,v) (i>1, v<w[i-1])

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高級算法之動態規劃實例分析

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com