01背包學習筆記 | 梓旭的藏書閣

status

date

slug

01 背包

有件物品和容量為的背包，每件物品只能使用一次。第件物品的體積為，價值為。求將哪些物品放入背包，可獲得不超過背包容量情況下的最大價值

首先可以使用二維陣列來儲存當只考慮前個物品且背包容量為時，該狀態符合題目條件下可獲得的最大價值。

也因此可以推出轉移式如下：

前者為不取第個物品的狀態，後者則是拿取第個物品，因此要讓容量減去第個物品的體積，讓總價值加上第個物品的價值。

接著要定義二維陣列的初始值，當沒有物品()時，能獲取的最大價值為，當背包容量為0()時，能獲取的最大價值也是0。

至於只考慮第一個物品()時，能獲取的最大價值則是取決於當前的背包容量是否超過

因此可以寫出以下的程式碼：

這邊是為了方便說明一開始的定義是只考慮前個物品，因此從 1-index 開始計算，使得多宣告了一個 row 之外，還要讓轉移式中的做 -1 的動作，其實可以寫得更加直觀：

上述程式的時間複雜度為，空間複雜度為。

雖然時間上已經無法再優化，但空間上我們還可以優化成。

仔細觀察轉移式會發現的狀態實際上只跟有關，因此可以使用兩個一維的陣列來記錄當前狀態以及前一維狀態，再滾動更新即可。

如果上述的程式碼的修改看起來與原本的做法差異過大而導致理解上有困難，這邊推薦一種叫做滾動數組的方式，從原本的程式碼修改只需要兩個步驟，不需要太多思考是該種做法極大的優點。

修正完的結果如下：

這種修改方式非常巧妙，運用了奇偶數的特性來不斷交錯兩個 row，且在修改程式法上非常輕鬆，推薦大家可以時常運用該種技巧。

（可將替換成，也可以達成相同的效果，但運算通常比更快）

雖然在上面我們已經成功將空間複雜度壓縮至，但實際上我們還能夠進一步優化至。

雖然在大多數情況下這樣的優化並沒有太大的區別，但將二維陣列壓縮至一維陣列的技巧是其他背包問題的基礎，因此仍然有學習的價值。

為了方面展示，這邊還是以與版本的程式碼舉例說明，如下圖所示：

可以看到的來源皆是在於的左邊，也就是說當我們從右邊開始 iterate 到左邊時，可以直接在原地執行操作，不需要再額外宣告上一個狀態的陣列。