一、學習目標

• 理解兩大類背包：0/1（每件最多一次）vs 完全（可重複拿）。
• 會寫出正確的雙迴圈順序，避免重複/漏算：
  • 0/1：容量倒序。
  • 完全：容量正序。
• 能處理三種常見目標：最大化、最小化、計數（排列/組合）。

二、觀念說明

差異

• 0/1 背包：每件只能取 0 或 1 次。例：每本書只能買一本。
• 完全背包：同一種物品可取多次。例：硬幣換錢。

雙迴圈順序

• 0/1：外層枚舉物品，內層容量倒序（避免同一輪把同物品用多次）。
• 完全：外層枚舉物品，內層容量正序（允許多次疊加）。

三種目標的典型轉移

• 最大化：dp[c] = max(dp[c], dp[c - w] + val)
• 最小化：dp[c] = min(dp[c], dp[c - w] + 1)（或 +cost）
• 計數（組合/順序）：
  • 組合（順序不重要）：外層物品、內層容量正序。
  • 排列（順序重要）：外層容量、內層物品。

細節

• 計數常需 MOD = 1e9+7；最小化要準備 INF。
• 盡量用一維滾動陣列（更快更省記憶體）。

三、CSES實戰演練

題目1:Book Shop

原題:
https://cses.fi/problemset/task/1158

題意：
n 本書，每本價格 h[i]、頁數 s[i]，預算 x，求最多能拿到幾頁。

解題思路：
0/1 背包；容量倒序更新。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, x; 
    cin >> n >> x;
    vector<int> h(n), s(n);
    for (int i=0; i<n; i++) cin >> h[i];
    for (int i=0; i<n; i++) cin >> s[i];

    vector<int> dp(x+1, 0); // dp[c] = 在預算 c 下的最大頁數
    for (int i = 0; i < n; i++) {
        for (int c = x; c >= h[i]; c--) {
            dp[c] = max(dp[c], dp[c - h[i]] + s[i]);
        }
    }
    cout << dp[x] << "\n";
    return 0;
}

題目2:Coin Combinations I

原題:
https://cses.fi/problemset/task/1635

題意：
給 n 種硬幣面額與目標和 x，問有幾種序列（順序視為不同）能湊成 x，答案對 1e9+7 取模。

解題思路：
排列計數 → 外層容量、內層硬幣；dp[0]=1。

#include<bits/stdc++.h>
using namespace std;
const int MOD=1000000007;

int main(){
    int n,x;
    cin>>n>>x;
    vector<int> coin(n);
    for(int i=0;i<n;i++){
        cin>>coin[i];
    }
    vector<int> dp(x+1,0);
    dp[0]=1;  //0元:都不拿

    // 順序有差:金額在外，硬幣在內

    // 要湊 9，最後一枚是 5 → 需要湊 4 (2+2)
    // → 組合 = 2+2+5
    // 要湊 9，最後一枚是 2 → 需要湊 7 (2+5 or 5+2)
    // → 組合 = 2+5+2, 5+2+2
    for(int i=1;i<=x;i++){
        long long ways=0;
        for(int c:coin){
            if(i>=c){
                ways+=dp[i-c];
            }
        }
        dp[i]=ways%MOD;
    }
    cout<<dp[x]<<endl;
    return 0;
}

四、Leetcode實戰演練

題目1:Partition Equal Subset Sum

原題:
https://leetcode.com/problems/partition-equal-subset-sum/description/

題意：
能否把陣列分成兩個子集且總和相等？

解題思路：

• 總和 S 必須偶數
• 問題等價「是否能選一些數湊成 target = S/2」→ 0/1 背包布林版
• 容量倒序。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        long long S = 0;
        for (int v:nums) S+=v;
        if (S % 2) return false;
        int target = (S/2);

        vector<char> dp(target+1, 0);
        dp[0] = 1;
        for (int v : nums) {
            for (int s = target; s>=v; s--) {
                dp[s] = dp[s] || dp[s-v];
            }
        }
        return dp[target];
    }
};

題目2:Coin Change II（完全背包：組合計數）

原題:
https://leetcode.com/problems/coin-change-ii/

題意：
用硬幣組成 amount 的組合數（順序不重要）。

解題思路：
外層硬幣、內層容量正序；dp[0]=1。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<unsigned long long> dp(amount+1, 0);
        dp[0] = 1;                         
        for (int c : coins) {  // 組合：外層枚舉硬幣
            for (int s = c; s <= amount; s++) { // 容量正序允許同幣多次
                dp[s] += dp[s-c];
            }
        }
        return dp[amount];
    }
};