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

status

date

slug

完全背包

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

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

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

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

寫成程式碼如下：

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

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

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

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

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

01 背包的轉換方程式：

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

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

也就是由大到小進行 Iterate

完全背包的轉移方程式：

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

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

也就是由小到大進行 Iterate

程式碼如下：