傳統背包筆記整理 | 梓旭的藏書閣

status

date

slug

前言

這是我在學習背包問題時，為了方便自己理解而隨手寫下的筆記，主要參考資料來源是宮水三葉大姊的背包問題詳解，但有些地方根據自己的習慣以及理解有些許微調，如果有寫得不清楚的地方歡迎來信指教或是直接去看三葉姊的原文。

01 背包

經典原型

題目描述

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

解題思路

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

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

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

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

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

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

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

空間優化 1

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

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

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

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

將的初始大小改成

將原先所有的改成

修正完的結果如下：

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

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

空間優化 2

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

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

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

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

練習

LeetCode 416

LeetCode 494

完全背包

經典原型

題目描述

有種物品和容量為的背包，每種物品可以無限次被重複挑選。第件物品的的體積是 , 價值是求將哪些物品放入背包可使總體積不超過背包的容量，且價值總和最大。

解題思路

其實就是將 01 背包的問題延伸至重複挑選的情況下，因此狀態定義也是同樣表示只考慮前件物品時，放入容量為的背包時可以獲得的最大價值。

轉移方程也是類似，這邊列出前幾個狀態的方程式：

選擇 0 件物品

選擇 1 件物品

選擇 2 件物品

選擇件物品

因此，我們可以得到轉移式為：

寫成程式碼如下：

空間優化 1

前面已經介紹過兩種優化至的方式，這邊就不再贅述直接實作：

空間優化 2

當然這邊也是能夠以空間複雜度實作，不過這邊優化的方式就跟 01 背包不太一樣了。

因為本人能力有限，因此這邊引用宮水三葉大神的證明QQ

畫成圖大概會長這個樣子：

在上圖的證明中，我們可以看到簡化轉移方程式之後，除了將空間複雜度從壓縮成以外，也成功地將時間複雜度從優化成了。

小結

01 背包的轉換方程式：

因為計算時，狀態取決於，

因此要確保先更新狀態才能更新，

也就是由大到小進行 Iterate

完全背包的轉移方程式：

因為計算時，狀態取決於，

因此要確保先更新狀態才能更新，

也就是由小到大進行 Iterate

程式碼如下：

練習

LeetCode 279

LeetCode 322

LeetCode 518

多重背包

經典原形

問題描述

有種物品和一個容量為的背包，每種物品的數量有限，第件物品的體積為，價值為，數量為，問分別選擇哪些物品多少件可以獲得最大的總價值

解題思路

同樣先套用01背包的意義:只考慮前件物品時，容量為的背包可獲得的最大價值。

列出取得不同數量的前幾個狀態，可以列出下面的方程式：

選擇 0 件物品

選擇 1 件物品

選擇 2 件物品

選擇件物品

因此可以得出以下的狀態轉移式：

可以看到多重背包的轉移式和完全背包一模一樣，差別只在多了對的限制條件不能超過。

概念上也就是完全背包有無限數量的物品，多重背包因為有限量，所以需要做限制。

時間複雜度：

空間複雜度：

空間優化 1

空間優化 2

在完全背包中，優化空間複雜度的同時，我們也將時間複雜度優化到了，然而在多重背包中，這種作法只能優化空間複雜度，對於時間複雜度則是無能為力。

當我們過去在完全背包中優化空間複雜度時，

我們能夠將簡化成了，

是因為每種物品分別都有無限種，只要保證是最優解，也就必定最優。

但在多重背包中，此解沒有辦法紀錄每種物品分別選取的數量，也就必須要保留該資訊。

因此在多重背包中，我們在從大到小做 Iterate 時，仍然需要保留對的計算。

二進制優化

多重背包問題實際上可以轉換成 01 背包問題，只是普通的轉換並沒有辦法真正起到優化的作用。

假設今天有一個物品最多能夠選擇次，對他做多重背包問題其實相當於對他做次 01 背包問題。

也可以想成在物品選項中變成了價值與體積皆相同的個物品，每個只能被選擇一次。

然而這樣轉換後的時間複雜度終究是，因此我們要在轉換上做一些調整。

在二進制的世界中，表達介於為到的任意數字，只需要個位元即可。

舉個例子，3 個位元能夠窮舉出 000, 001, 010, 011, 100, 101, 110, 111 八種結果，分別對應 0 到 7。

因此如果我們在轉換中將選擇次數為的物品，轉換成種物品，時間複雜度自然能夠下降。

而扁平化的方式也很簡單，只需要盡量用 2 的冪次來描述即可。

假設，我們能夠以來描述，原本轉換成 10 個價值為與體積為皆與原本相同的物品，現在只需要 4 個物品()，分別是，就可以枚舉出所有該物品被拿取次的情況。

假設該物品被選擇 6 次，只需挑選總價值為，總體積為，也就是即可，其他情況請自行舉一反三。

如此一來，就能夠將在多重背包的問題轉換成 01 背包的同時，降低時間複雜度。

簡單寫成程式碼如下：

時間複雜度：

空間複雜度：

註：即扁平化後有多少種物品。

單調佇列優化

學不會QQ

學會之後再補，如果我沒有忘記的話。

混合背包

前言

這篇筆記只是單純紀錄前面三種背包的題型整理，就當作練習啦。

傳統的背包題目就到此告一個段落了，其他的背包就不再是如此單純的題目，

因此究竟我的筆記會不會延續下去也是另外一個問題._.

最近很想鬼轉另外一篇學習計畫w

題目描述

給定物品數量為和容量為的背包，第件物品的價值為，體積為，可用數量為。當時，代表該物品只能使用一次。當時，代表該物品可以使用無限次。當為任意正整數時，代表該物品可以使用次。求不超過背包容量的情況下，能夠獲得的最大總價值。

思路分析

我們知道多重背包可以用二進制優化壓縮成 01 背包，所以實際上我們只需要判斷 01 背包與完全背包，再根據各自的轉移式得出答案即可。