【C++】競程筆記（背包問題 習題練習）

練習題目參考自：NTUCPC Guide，此筆記僅為個人學習用途。

電車遊戲

這道題是 0/1 背包問題或集合劃分的變形題。

Problem Source：https://oj.ntucpc.org/problems/803

該題目標是將 $N$ 個移動距離 $a_i$ 分配到兩個集合中：一個集合是「向左走（$X$軸）」，另一個集合是「向上走（$Y$軸）」。

設所有 $a_i$ 的總和為 $S$，且向左走的總距離為 $x$，那麼向上走的總距離就是 $S - x$。

題目要求最小化距離的平方：$x^2 + (S - x)^2$。

1. 定義狀態：Boolean 陣列 $dp[j]$ 為是否能夠湊出總和為 $j$ 的移動距離。
   • 若 $dp[j]$ 為 true，表示可從給定的數字中選出若干個，使其總和剛好為 $j$（作為 $X$ 軸的移動距離）。
2. 定義轉移式：

對每個新移動距離 $v$（為輸入的 $a_i$），更新所有可能的 $j$。

若在之前的步驟中已能湊出 $j$（$dp[j] = true$)，則加上現在的 $v$ 後，即可湊出 $j + v$。

因此，

• 若選 $v$ ，狀態則是 $dp[j - v]$ 。（選 $v$ 之前能湊出 $j-v$）
• 若不選 $v$ ，則狀態依然是 $dp[j]$ 。（不選 $v$ 就能湊出 $j$）

最後得到完整轉移式：$$dp[j] = dp[j] \lor dp[j - v]$$

3. 定義初始狀態：$dp[0] = \text{true}$ ，其餘都是 false。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

const int MAXS = 500005; // N = 1000, a_i = 500, MAXS = N * a_i
bool dp[MAXS];

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    vector <int> a(N);
    int total_sum = 0;
    for (int i = 0; i < N; ++i){
        cin >> a[i];
        total_sum += a[i];
    }
    
    dp[0] = true;
    
    for (int i = 0; i < N; ++i){
        int v = a[i];
        for (int j = total_sum; j >= v; --j)
            dp[j] = dp[j] || dp[j - v];
    }
    
    long long ans = -1; // 因為距離平方肯定為 0 或正, 故設 -1
    // 找到一個 x 使 x^2 + y^2 最小
    for (int x = 0; x <= total_sum; ++x){
        if (dp[x]){
            long long y = total_sum - x;
            long long curr_dist = (long long)x * x + y * y;
            
            // ans == -1 的判斷是表示要先找到一個合法解
            // curr_dist < ans 找最小值
            if (ans == -1 || curr_dist < ans) ans = curr_dist;
        }
    }
    
    cout << ans << '\n';
}

APCS 2018/10 P4 置物櫃出租

該題為 0/1 背包問題的變形題。

Problem Source：https://oj.ntucpc.org/problems/804

題目要求最小化「被退租客戶的容量總和」，等同於要最大化「被保留客戶的容量總和」。

因此思路就可以轉換。

• 限制條件：王老先生需要 $S$ 個格子，置物櫃總共有 $M$ 個格子，因此，能夠留給客戶的最大空間為 $Limit = M - S$。
• 目標：在不超過 $Limit$ 的容量限制下，盡可能塞入最多的客戶容量。
• 計算結果：全部客戶原本的總容量 - 在 $Limit$ 限制下能保留的最大容量 = 最小損失。

1. 定義狀態： $dp[j]$ 為容量限制 $j$ 的情況下，所能裝入客戶物品的最大容量和。（根據題目，在此的價值等同於容量）
2. 定義轉移式：

對每個客戶 $i$（容量為 $v$），決定要不要留他，假設容量 $j$ 足夠放入該客戶（$j \ge v$），可選擇：

• 不保留： $dp[j]$
• 保留： $dp[j - v] + v$

取最大值得到完整轉移式：$$dp[j] = \max(dp[j], \quad dp[j - v] + v)$$

由於每個客戶只能選一次，因此內層迴圈需由大到小遍歷（由 $Limit$ 遞減到 $v$），以避免重複選取同一個物品。

3. 定義初始狀態： $dp[0 ... j]$ 全都 0。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int n, M, S;
    cin >> n >> M >> S;
    
    vector <int> f(n);
    int total_occupied = 0;
    
    for (int i = 0; i < n; ++i){
        cin >> f[i];
        total_occupied += f[i];
    }
    
    int limit = M - S;
    
    if (total_occupied <= limit){
        cout << 0 << '\n';
        return 0;
    }
    
    vector <int> dp(limit + 5, 0);
    for (int i = 0; i < n; ++i){
        int v = f[i];
        
        for (int j = limit; j >= v; --j){
            dp[j] = max(dp[j], dp[j - v] + v);
        }
    }
    
    cout << (total_occupied - dp[limit]) << '\n';
}

Minimizing Coins

此題為 DP 著名的「零錢兌換問題」。

Problem Source：https://cses.fi/problemset/task/1634

1. 定義狀態： $dp[i]$ 為湊成金額 $i$ 所需的最少硬幣數量。
2. 定義轉移式：

要算湊成金額 $i$ 的最少硬幣數，可以考慮最後加入的那一枚硬幣是哪一種。

假設硬幣面額集合 $C = \{c_1, c_2, \dots, c_n\}$

若選擇硬幣 $c_j$ 作為最後一枚硬幣，則剩下的金額為 $i - c_j$，此時的硬幣總數就是 $dp[i - c_j] + 1$。

為了求最少數量，則遍歷所有可能的硬幣面額，找出最小值：$$dp[i] = \min_{c \in C} (dp[i - c]) + 1$$

註：當 $i - c \ge 0$ 時才能轉移。

3. 定義初始狀態：
   • 金額 = 0， $dp[0] = 0$
   • 其餘金額，$dp[1 \cdots x] = INF$ or 極大值（x 為湊出的目標金額）

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    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, INF);
    
    dp[0] = 0;

    for (int i = 1; i <= x; ++i){
        for (int c : coin)
            if (i - c >= 0)
                dp[i] = min(dp[i], dp[i - c] + 1);
    }
    
    cout << (dp[x] == INF ? -1 : dp[x]) << '\n';
}

Coin Combinations I

Problem Source：https://cses.fi/problemset/task/1635

該題與上題類似，只是從原本要求用「最少硬幣數」湊出目標金額，變成求「有幾種方法數」可湊出目標金額。

注意題目說順序不同的組合被視為不同的方法（如 1+2 和 2+1 是不同的方法）。（該題為求排列數方法）

1. 定義狀態：$dp[i]$ 為湊成金額 $i$ 的方法數。
2. 定義轉移式：

假設要湊成金額 $i$，最後一步可加上任何一種面額的硬幣 $c$。

如果最後加上的硬幣是 $c$，則先前的金額一定是 $i-c$。因此，湊成金額 $i$ 的方法數，就是所有能透過加上一枚硬幣到達 $i$ 的前一個狀態的方法數總和。

完整轉移式：$$dp[i] = \sum_{c \in C} dp[i - c]$$

條件：$i - c \ge 0$

3. 定義轉移式： $dp[0] = 1$ ，當金額為 0 時只有一種方法數，其他初始化為 0。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    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;
    
    for (int i = 1; i <= x; ++i){
        for (int c : coin)
            if (i - c >= 0)
                dp[i] = (dp[i] + dp[i - c]) % MOD;
    }
    
    cout << dp[x] << '\n';
}

Coin Combinations II

Problem Source：https://cses.fi/problemset/task/1636

與上題相似，但這題改求組合方法數，因為順序不同的組合視為同一種方法（如 1+2 和 2+1 是相同的）。

1. 定義狀態：$dp[i]$ 為湊成金額 $i$ 的有序組合方法數。
2. 定義轉移式：

原本 Coin Combinations I 是因為不同順序也算一種方法數，所以外層是從 1 遍歷到 x，內層遍歷 coin。

而在 Coin Combinations II 這個問題中，順序不同算是同一種方法，因此得將遍歷的順序對調，改成外層遍歷 coin，內層遍歷 1 到 x。

在轉移式上還是一樣的：$$dp[i] = \sum_{c \in C} dp[i - c]$$

條件：$i - c \ge 0$

3. 定義初始狀態：同上題。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    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;
    
    for (int c : coin){
        for (int i = 1; i <= x; ++i)
            if (i - c >= 0)
                dp[i] = (dp[i] + dp[i - c]) % MOD;
    }
    
    cout << dp[x] << '\n';
}