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

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

最後更新時間：

什麼是背包問題

背包問題（Knapsack Problem）是一種組合最佳化的 NP-Complete 問題，有著多種變形，其中最基礎的是「0/1 背包問題」。

在 DP 裡面，背包問題是最經典且常見的題型之一。

01 背包問題

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

所謂 0 1 就是物品可拿或不拿。

題目敘述：

有 NN 個物品編號 1∼N1 \sim N ，第 ii 個物品的重量和價值分別是 wiw_i 和 viv_i 。學姐打算從這 NN 個物品選其中一些帶走，但她只有大小為 WW 的背包，也就是說她選擇的物品總重不能超過 WW 。請問背包能容納的物品的總價值最大是多少？

如果直接定義 dp[i]dp[i] 是前 ii 個物品的最大總價值，是不實際的，因為還要考慮到 WW 重量的因素。

因此用到二維 DP 觀念：dp[i][j]dp[i][j] 為前 ii 個物品且背包當前容量限制為 jj 時，能獲得的最大價值。

對於第 ii 個物品（重量 w[i]w[i]，價值 v[i]v[i]），當考慮是否要放入背包（當前容量 jj）時，只有兩種選擇：

  1. 不拿第 ii 個物品：最大價值 = 前 i−1i - 1 個物品且容量為 jj 的最大總價值。$$dp[i][j] = dp[i-1][j]$$
  2. 拿第 ii 個物品：前提是背包要夠裝 （j≥w[i]j \ge w[i]），如果拿了，會得到 v[i]v[i] 的價值，但背包容量會減少 w[i]w[i]。剩下的容量 j−w[i]j - w[i] 就要去查詢「前 i−1i-1 個物品」能湊出的最大價值。$$dp[i][j] = dp[i-1][j - w[i]] + v[i]$$

由於要求最大價值，因此 $$dp[i][j] = \max(dp[i-1][j], \quad dp[i-1][j - w[i]] + v[i])$$

最後在 base case 定義上，設定為全部都是 0。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 105;
const int MAXW = 100005;
const int INF = -1e9;

long long dp[MAXN][MAXW];

int w[MAXN], v[MAXN];

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, wmax;
    cin >> n >> wmax;
    
    for (int i = 1; i <= n; ++i) cin >> w[i] >> v[i];
    
    for (int i = 1; i <= n; ++i){
        for (int j = 0; j <= wmax; ++j){
            if (j < w[i]){
                dp[i][j] = dp[i - 1][j];
            }
            else{
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    cout << dp[n][wmax] << '\n';
}

0/1 背包問題變形：鐵棒問題

此為經典的子集合加總問題（Subset Sum Problem），屬於 0/1 背包問題的變形。

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

  1. 定義狀態： dp[i][j]dp[i][j] 是一個布林值，其意義為從前 ii 條鐵棒中選出若干條，使其長度總和恰好為 jj，則為 true；否則為 false。
  2. 定義轉移式：

對於第 ii 條鐵棒（其長度為 lil_i），有兩種選擇：

  • 不選這條鐵棒：如果前 i−1i-1 條鐵棒能湊出長度 jj，那前 ii 條當然也能。$$dp[i-1][j]$$
  • 選這條鐵棒：前提是目標長度 jj 必須大於等於鐵棒長度 lil_i，如果選了，問題就變成「前 i−1i-1 條鐵棒能否湊出長度 j−lij - l_i」。$$dp[i-1][j - l_i] \ , (j \ge l_i)$$

完整轉移式：$$dp[i][j] = dp[i-1][j] \lor dp[i-1][j - l_i]$$

當中 ∨\lor 表示 OR，其中一個可以湊出長度 jj 就行。

  1. 定義初始狀態：沒鐵棒時（i=0i=0）：
    • 湊出長度為 0 是可能的（一條都不選）：dp[0][0]=truedp[0][0] = \text{true}
    • 湊出任何大於 0 的長度是不可能的：dp[0][j]=falsedp[0][j] = \text{false} （for j>0j > 0）

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>

using namespace std;

const int MAXN = 35;
const int MAXL = 1005;

bool dp[MAXN][MAXL];

int l[MAXL];

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int t;
    cin >> t;
    while(t--){
        int L, N;
        cin >> L >> N;
        for (int i = 1; i <= N; ++i) cin >> l[i];
        
        dp[0][0] = true;
        
        for (int i = 1; i <= N; ++i){
            for (int j = 0; j <= L; ++j){
                bool not_pick = dp[i - 1][j];
                
                bool pick = false;
                if (j >= l[i]) pick = dp[i - 1][j - l[i]];
                
                dp[i][j] = not_pick || pick;
            }
        }
        
        cout << (dp[N][L] ? "TAK\n" : "NO\n");
    }
}

0/1 背包問題變形：高棕櫚農場

Problem Source：https://tioj.sprout.tw/problems/143

為什麼是背包問題？

在有限的飽足感容量（ MM ）限制下，選擇若干個高棕櫚（物品），使得總滿足感（價值）最大化。

  1. 定義狀態：令 dp[j]dp[j] 表示當飽足感上限為 jj 時，能夠獲得的最大滿足感。（原問題可用二維 dp 做，但會超時，因此在這邊將狀態壓縮成一維）
  2. 定義轉移式：

對於每個高棕櫚 ii（其飽足感為 AiA_i，滿足感為 BiB_i）有兩種選擇：

  • 不吃：最大滿足感保持不變，即 dp[j]dp[j]。
  • 吃：需要消耗 AiA_i 的飽足感，因此目前的滿足感會變成「剩餘容量 j−Aij - A_i 時的最大滿足感」加上「當前高棕櫚的滿足感 BiB_i」，即 dp[j−Ai]+Bidp[j - A_i] + B_i。

則取兩種選擇的最大值即為轉移式：$$dp[j] = \max(dp[j], \quad dp[j - A_i] + B_i)$$

  1. 定義初始狀態：滿足感全 0（dp[0⋯M]=0dp[0 \cdots M] = 0）。

範例程式碼：

由於每個物品只能選一次，在用一維 dp 計算時，內層迴圈須由大到小（從 MM 遞減到 AiA_i）遍歷，這樣可確保計算 dp[j]dp[j] 時所參考的 dp[j−Ai]dp[j - A_i] 是來自「上一個物品」的狀態，而不是「當前物品」已經被選過之後的狀態。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N, M;
    
        cin >> N >> M;
    
        vector<int> A(N), B(N);
    
        for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    
        vector<int> dp(M + 1, 0);
    
        for (int i = 0; i < N; ++i) {
            int w = A[i];
            int v = B[i];
    
            for (int j = M; j >= w; --j)
                dp[j] = max(dp[j], dp[j - w] + v);
        }
    
        cout << dp[M] << '\n';
    }
    return 0;
}

0/1 背包問題變形：高棕櫚農場2

Problem Source：https://tioj.sprout.tw/problems/144

在原本的架構上，這題又給你加一個限制： KK ，吃掉高棕櫚的上限。

解題邏輯跟上題差不多，不管物品 ii 的維度，只關心 M,KM, K 的維度即可，此為滾動 DP 優化空間的做法。

  1. 定義狀態：令 dp[j][k]dp[j][k] 為當前飽足感為 jj，且吃了 kk 個高棕櫚時，所能獲得的最大滿足感。
  2. 定義轉移式：

對於每個高棕櫚 ii（其飽足感為 AiA_i，滿足感為 BiB_i）有兩種選擇：

  • 不吃：狀態維持不變，即 $$dp[j][k]$$
  • 吃：前提是當前飽足感 j≥Aij \ge A_i 且數量 k≥1k \ge 1。此時滿足感為由「飽足感 j−Aij-A_i 且數量 k−1k-1」的狀態加上當前的滿足感 BiB_i，即 $$dp[j-A_i][k-1] + B_i$$

完整轉移式： $$dp[j][k] = \max(dp[j][k], \quad dp[j - w][k - 1] + v)$$

  1. 定義初始狀態：跟上題一樣，dp 全 0。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--){
        int N, M, K;
        cin >> N >> M >> K;
        
        vector <vector <int>> dp(M + 1, vector<int>(K + 1, 0));
        
        vector<int> A(N), B(N);
    
        for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];
        
        for (int i = 0; i < N; ++i){
            int w = A[i];
            int v = B[i];
            
            for (int j = M; j >= w; --j){
                for (int k = K; k >= 1; --k){
                    dp[j][k] = max(dp[j][k], dp[j - w][k - 1] + v);
                }
            }
        }
        
        cout << dp[M][K] << '\n';
    }
}

背包問題的另種形式：無限背包問題（Unbounded Knapsack Problem）

無限背包問題又稱為完全背包問題，與 0/1 背包問題不同的是：完全背包問題的每種物品的數量是無限的，只要背包裝得下，同一種物品可選 1 個、2 個，甚至無限個。

接下來請看問題。

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

:::info
Description

現在有 NN 個物品，第 ii 個物品的重量為 wiw_i ，價值為 viv_i 。每個物品都有無限多個。你有一個重量限制為 WW的背包，你希望可以在不超過這個背包重量限制的前提下，盡可能塞入價值總和最高的物品。請問你可以塞入最高的物品總價值是多少？
:::

  1. 定義狀態： dp[j]dp[j] 為當背包重量總和為 j 時所能裝入物品的最大價值總和。所求的解為 dp[W]dp[W] ，背包最大重量限制。
  2. 定義轉移式：
    • 不選：價值不變，仍為 dp[j]dp[j] 。
    • 選：選後背包剩餘可裝重量為 j−wij - w_i 。此時的價值就是「容量為 j−wij - w_i 時的最大價值」加上「當前物品的價值 viv_i」。

最終得到完整轉移式：$$dp[j] = \max(dp[j], \quad dp[j - w_i] + v_i)$$

  1. 定義初始狀態：全都是 0。

範例程式碼：

可發現在 0/1 背包問題中，內層迴圈往往都是以「逆序」遍歷，也就是 W→wiW \rightarrow w_i 的走訪。

但到了無限背包問題，就會相反過來變成「正序」遍歷（ wi→Ww_i \rightarrow W ）

差別在於 0/1 背包問題每個物品都只能取一次，而無限背包可以無限取，也就是每件物品可以重複取的意思，因而需要將無限背包改成正序遍歷。

  • 正序（無限背包）：計算 dp[j]dp[j] 時， dp[j−wi]dp[j-w_i] 是新狀態，可能已包含當前物品。
  • 逆序（0/1 背包）：計算 dp[j]dp[j] 時， dp[j−wi]dp[j-w_i] 是舊狀態，不包含當前物品。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int N, W;
    cin >> N >> W;
    
    vector <int> w(N), v(N);
    for (int i = 0; i < N; ++i) cin >> w[i];
    for (int i = 0; i < N; ++i) cin >> v[i];
    
    vector <long long> dp(W + 1, 0);
    for (int i = 0; i < N; ++i)
        for (int j = w[i]; j <= W; ++j)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    
    cout << dp[W] << '\n';
}