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

status

date

slug

混合背包

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

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

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

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

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

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