《背包九講》學習筆記（未完待續）

背包九講下載下傳位址

1. 01 背包問題

描述

n 個物品放進容量為v的背包，第 i 個物品的價值為wi，花費為 ci ，問能裝入物品的最大總價值。

核心代碼

///dp[j]為前i個物品裝在容量為j的背包内可以産生的最大總價值
int dp[v + ] = {};
for(int i = ; i < n; ++i) {
    for(int j = v; j >= c[i]; --j) {
         ///對于每個物品i，對于容量j，判斷是否從容量j-c[i]的背包加上一個i物品轉移來更優
        dp[j] = max(dp[j],dp[j - c[i]] + w[i]);
    }
}
           

複雜度

• 時間複雜度

  O(vn)

• 空間複雜度

  O(v)

例題

待續
           

備注

初始化：

• 當不要求全部裝滿背包時，全部初始化為0
• 當要求全部裝滿背包時，dp[0]初始化為0，其餘的初始化為-INF
• 各類背包可參照該初始化技巧

與完全背包在寫法上的差別：

• j 從v遞減到 ci ，因為每次隻會通路下标比j小的dp值，故這樣可以保證每種物品最多被取一次

2. 完全背包問題

描述

n 種物品各無限個放進容量為v的背包，第 i 種物品每個的價值為wi，花費為 ci ，問能裝入物品的最大總價值。

核心代碼

///dp[j]為前i種物品裝在容量為j的背包内可以産生的最大總價值
int dp[v + ] = {};
for(int i = ; i < n; ++i) {
    for(int j = c[i]; j <= v; ++j) {
        ///對于每個物品i，對于容量j，判斷是否從容量j-c[i]的背包加上一個i物品轉移來更優
        dp[j] = max(dp[j],dp[j - c[i]] + w[i]);
    }
}
           

複雜度

• 時間複雜度

  O(vn)

• 空間複雜度

  O(v)

例題

• POJ 1384 Piggy-Bank

  AC代碼

備注

與01背包在寫法上的差別：

• j 從ci遞增到 v <script type="math/tex" id="MathJax-Element-20">v</script>，當通路下标比j小的dp值時，該值可能是已經加入了物品i而産生的，故這樣可以使每種物品被取多次