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

status

date

slug

多重背包

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

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

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

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

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

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

時間複雜度：

空間複雜度：

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

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

我們能夠將簡化成了，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

簡單寫成程式碼如下：

時間複雜度：

空間複雜度：

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

學不會QQ

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