背包 DP (Knapsack DP)
0-1 背包問題
0-1 背包問題
給定 個物品的重量 和價值 ,和一個容量為 的背包。選取若干件物品放入背包,在不超過背包容量的情況下,背包內物品價值總和最大為何?
每種物品有兩個狀態不放與放,可對應二進位的 和 ,故稱為「0-1 背包問題」。
題目有三項資料,物品個數、物品重量、物品價值,利用這些資料設計出狀態式:
- 狀態: 代表前 樣物品在重量總和 的情況下,物品價值總和最大值。
- 初始狀態: 。
當算好 個物品的狀態,對於第 個物品有兩種選擇
- 不放:重量和價值不變 。
- 放:重量 ,價值 。
轉移式就由上面兩種選擇歸納出:
- 。
以下為利用二維陣列儲存答案的範例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
滾動陣列
空間複雜度 ,採用「滾動陣列」,可以降低空間複雜度
由上圖可得知,當在計算 時,只會用到上一列的資料,因此我們的需要陣列大小降到 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
再來,如果我們將 當中的 由大到小計算。
會發現計算 時, 也不會用到,可以將 覆蓋到 上面。我們可以再次縮小陣列,變成大小為 的一維陣列。
1 2 3 4 5 6 7 8 9 |
|
滾動陣列
覆蓋不會用到的資訊,降低記憶體使用量。
0-1 背包問題時間複雜度 ,空間複雜度 。
背包問題另一種狀態式
這題的 範圍在 ,用上述的狀態式肯定 TLE
,因此我們將狀態式改成:
- 狀態: 代表前 樣物品在價值總和為 的情況下,重量總和最小值。
- 初始狀態: 。
轉移式改成:
最後找出:
技巧:表示(負)無限大
(負)無限大只要設成一個比最大(小)答案還要大(小)的值就行了。
無限背包問題
無限背包問題
給定 種物品的重量 和價值 ,和一個容量為 的背包。每種物品可選取任意個放入背包,在不超過背包容量的情況下,背包內物品價值總和最大為何?
無限背包問題和 0-1 背包問題差異在於無限背包的物品可以選無限多個。
無限背包問題和 0-1 背包問題的狀態式相同,以下為轉移式:
可以簡化成:
- 。
- 。
為什麼可以這樣優化?是因為當 當中的 由小到大計算時, 已被 更新過,那麼 就是選擇第 種物品數次的最佳結果。
換言之,我們通過局部最優子結構的性質重複使用了之前的枚舉過程,優化了枚舉的複雜度。(from 背包 DP - OI Wiki )
下面為範例程式碼,一樣有用到滾動陣列的技巧:
1 2 3 4 5 6 7 8 9 |
|
無限背包問題時間複雜度 ,空間複雜度 。