---
# System prepended metadata

title: 背包問題
tags: [好東西]

---

背包好好玩，所以把他分出來講。
寫背包問題，聽[你的背包](https://www.youtube.com/watch?v=s3AmqV6VlE0)。(注意 : 此方法有奇效。)

# [背包問題 (1)](https://dandanjudge.fdhs.tyc.edu.tw/ShowProblem?problemid=b216) (0/1背包)

首先你可以現去看[這部影片](https://www.youtube.com/watch?v=nLmhmB6NzcM&t=1s)，超有用。(但是他有一個缺點，看太多的話你英文的口音會被影響。)

:::success
0/1背包 的意思就是每個物品只能選 $0$ 次或 $1$ 次。
:::

---

### 暴力枚舉
看完影片之後你會知道 0/1背包 的第一種解法，暴力枚舉。(不看好像也會知道。)

DFS枚舉在這題可以拿到 $20\%$ ，其他都 $TLE$ ，因為他的時間複雜度是 $O(2^n)$ 。
:::info
:::spoiler DFS枚舉
```cpp=
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <cstdio>
#include <random>
#include <string>
#include <cstring>
#include <sstream>
#include <utility>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define int long long
#define endl "\n"
#define F first
#define S second
#define mkp make_pair
#define UID uniform_int_distribution
#define int_range numeric_limits<int>::min(), numeric_limits<int>::max()

using namespace std ;

int n , c , best = 0;
vector<int> w , v ;

void DFS(int i, int cur_w, int cur_v){
    if (i == n){
        // 所有物品都考慮完，更新最優值。
        best = max(best , cur_v) ;
        return ;
    }
    
    // 不選第 i 件。
    dfs(i + 1, cur_w, cur_v);

    // 在不超重的前提下選第 i 件。
    if (cur_w + w[i] <= c){
        dfs(i + 1 , cur_w + w[i] , cur_v + v[i]) ;
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) ;

    cin >> n >> c ;
    
    w.resize(n) ;
    v.resize(n) ;
    for (int i = 0 ; i < n ; i++){
        cin >> w[i] >> v[i] ;
    }

    DFS(0, 0, 0) ;
    cout << best << endl ;
    
    return 0 ;
}

```
:::

二進制遮罩枚舉送出後是 $0\%$，其中有一筆 $TLE$ ，因為他的時間複雜度也是 $O(2^n)$ 。

其他筆會看到輸出 $0$ ，是因為他來不及跑出答案，對，真的。

:::info
:::spoiler 二進制遮罩枚舉 (Bitmask)
```cpp=
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <cstdio>
#include <random>
#include <string>
#include <cstring>
#include <sstream>
#include <utility>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define int long long
#define endl "\n"
#define F first
#define S second
#define mkp make_pair
#define UID uniform_int_distribution
#define int_range numeric_limits<int>::min(), numeric_limits<int>::max()

using namespace std ;

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) ;

    int n , c ;
    cin >> n >> c ;
    vector<int> w(n) , v(n) ;
    for (int i = 0 ; i < n ; i++){
        cin >> w[i] >> v[i] ;
    }

    int ans = 0 ;
    
    // 枚舉所有可能的子集。
    int total_mask = 1 << n ;
    for (int mask = 0; mask < total_mask ; mask++){
        int sum_w = 0 , sum_v = 0 ;
        // 遍歷遮罩的每一位，判斷是否選第 i 件物品。
        for (int i = 0 ; i < n ; i++){
            if (mask & (1 << i)){
                sum_w += w[i] ;
                sum_v += v[i] ;
            }
        }
        // 如果不超重，就嘗試更新答案。
        if (sum_w <= c){
            ans = max(ans, sum_v) ;
        }
    }

    cout << ans << endl ;
    
    return 0 ;
}

```
:::

#### 小結
就是會 $TLE$ ，因為他的 $n$ 最多到 $1000$ ，然後時間複雜度是 $O(2^n)$ ，所以是 $2^{1000} \approx 10^{301}$ 。

會炸掉很正常。

#### 提問
在我打這部分的時候，好電的 $timmy$ 問我說為什麼枚舉是用 DFS 和 二進制遮罩，其實原因就是因為我們枚舉的目的是 **列舉所有物品的選擇組合** ，會是 $O(2^n)$ 也就變得好理解了，因為每一個都有選或不選兩種選擇。

用 DFS 的原因是要遍歷一棵樹，一棵二叉樹，分為選或不選，一共有 $2^n$ 條路。

不用二進制遮罩可以改為 `bool used[n]`，但有一個很明顯的問題，記憶體佔用高。
所以改用二進制遮罩，用一個整數的二進位表示法，剛好可以完美記錄哪些物品被選過，選了是 `0` ，沒選是 `1` 。

---

### 二維DP
看完影片之後你會知道 0/1背包 的第二種解法，二維DP。在影片中細緻的解釋了他的做法和過程，並且用了表格和集合兩種方式來講解。

當你看完表格法時你就已經會二維DP的作法了。

:::info
:::spoiler 二維DP
```cpp=
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <cstdio>
#include <random>
#include <string>
#include <cstring>
#include <sstream>
#include <utility>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define int long long
#define endl "\n"
#define F first
#define S second
#define mkp make_pair
#define UID uniform_int_distribution
#define int_range numeric_limits<int>::min(), numeric_limits<int>::max()

using namespace std ;

signed main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) ;

    int n, c ;
    cin >> n >> c ;
    vector<int> w(n+1) , v(n+1) ;
    for (int i = 1 ; i <= n ; i++){
        cin >> w[i] >> v[i] ;
    }

    // dp[i][j]：前 i 件物品，容量不超過 j 時的最大價值。
    vector<vector<int>> dp(n+1 , vector<int>(c+1 , 0)) ;

    for (int i = 1 ; i <= n ; i++){
        for (int j = 0 ; j <= c ; j++){
            // 不選第 i 件。
            dp[i][j] = dp[i-1][j] ;
            // 在不超重的前提下選第 i 件。
            if (j >= w[i]){
                dp[i][j] = max(dp[i][j] , dp[i-1][j - w[i]] + v[i]) ;
            }
        }
    }

    cout << dp[n][c] << endl ;
    
    return 0 ;
}
```
:::

然後你會發現送出會是 $0\%$ ，全是 $RE$ 。

他的時間複雜度是 $O(nc)$ ，時間的確是不會爆。

但是他空間複雜度也是 $O(nc)$，`dp[1001][100001]` 把大約 $10^8$ 個 `long long` $（\approx800 \; MB）$ 的空間放在函數堆疊裡，然後因為系統最多只能設到 $512 \; MB$ 加上我沒有特別去改所以只有 $64 \; MB$ ，因此在他宣告時就會發生 $Stack \; Overflow$，系統回報 $Segmentation \; Fault$ 就非常開心的拿到 $RE$ 了。

至於想細部的了解 $Stack \; Overflow$ 的發生過程，去學 記憶體佈局，好玩。

#### 轉移式
$dp[i][j] = 
\begin{cases}dp[i-1][j], & \text{若 } j < w_i \\
\max\left(dp[i-1][j],\ dp[i-1][j - w_i] + v_i\right), & \text{若 } j \ge w_i
\end{cases}$

---

### 一維滾動DP
鋪墊那麼多，就是為了他。

很明顯，二維DP 解決不了這一題，所以我們需要把空間壓的更小。

如果你理解了 二維DP 在幹嘛並可以清楚的解釋他的流程，那你就會發現，他在運行時只會用到 **前一行的狀態 `dp[i-1][ ]`** 那就代表只要用一個一維陣列就可以了。

所以我們就:
```cpp=
for (int j = w[i] ; j <= c ; j++){
    dp[j] = max(dp[j] , dp[j - w[i]] + v[i]) ;
}
```

可是眼尖的你就發現了，這時的 `dp[j]` 是在處理完前 `i` 件物品後，容量為 `j` 的最大價值。

如果你沒有發現也不了解上面一句話是什麼意思，那你就是不理解上面那句話 :+1: 。

通俗一點的說，他是讓同一個物品可以被多次選取，也就是東西可能已經被用過了，而 0/1背包 的主軸就是 **最多只能放一次** 那就不行這樣做，他變成了 完全背包。

那怎麼辦 ?
::: warning
前面過不去，我們就從後面來。
:::

這句話是 0/1背包 的精髓，對，精髓。

因為當你倒著走時，還沒被更新的 `dp[j - w[i]]` 是前一輪（上一件物品）留下來的，所以你確保了每一個物品只能用一次。

:::danger
:::spoiler 如果還是聽不懂，這裡把步驟給剖析一次。
重量 : `w = 2`
價值 : `v = 10`
背包總容量 : `c = 5`

正序:
```cpp=
dp[0] = 0 ;
for (int j = 2 ; j <= 5 ; j++){
    dp[j] = max(dp[j] , dp[j - 2] + 10) ;
}
```
| j | dp\[j - 2]    | 更新後的 dp\[j]          |
| - | ------------- | -------------------- |
| 2 | dp\[0] = 0    | dp\[2] = 10          |
| 3 | dp\[1] = 0    | dp\[3] = 10          |
| 4 | dp\[2] = 10  | dp\[4] = 20 → 多選一次了  |
| 5 | dp\[3] = 10  | dp\[5] = 20 → 又多選一次了 |

最大價值為 $20$ 。

倒序:
```cpp=
dp[0] = 0 ;
for (int j = 5 ; j >= 2 ; j--){
    dp[j] = max(dp[j] , dp[j - 2] + 10) ;
}
```
| j | dp\[j - 2] | 更新後的 dp\[j] |
| - | ---------- | ----------- |
| 5 | dp\[3] = 0 | dp\[5] = 10 |
| 4 | dp\[2] = 0 | dp\[4] = 10 |
| 3 | dp\[1] = 0 | dp\[3] = 10 |
| 2 | dp\[0] = 0 | dp\[2] = 10 |

最大價值為 $10$ 。

:::

所以你會得到:
```cpp=
for(int j = c ; j >= w[i] ; j--){
    dp[j] = max(dp[j] , dp[j-w[i]]+v[i]) ;
}
```

:::info
:::spoiler 一維滾動DP
```cpp=
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <cstdio>
#include <random>
#include <string>
#include <cstring>
#include <sstream>
#include <utility>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

#define int long long
#define endl "\n"
#define F first
#define S second
#define mkp make_pair
#define UID uniform_int_distribution
#define int_range numeric_limits<int>::min(), numeric_limits<int>::max()

using namespace std ;

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) ;

    int n , c ;
    cin >> n >> c ;

    vector<int> w(n) , v(n) ;
    for(int i = 0 ; i < n ; i++){
        cin >> w[i] >> v[i] ;
    }

    vector<int> dp(c+1 , 0) ;
    for(int i = 0 ; i < n ; i++){
        for(int j = c ; j >= w[i] ; j--){
            dp[j] = max(dp[j] , dp[j-w[i]]+v[i]) ;
        }
    }

    cout << dp[c] ;

    return 0 ;
}
```
:::

時間複雜度是 $O(nc)$，空間複雜度是 $O(c)$，成功的減少了。

#### 轉移式

$\displaystyle dp[j] = \max(dp[j],\ dp[j - w_i] + v_i)$

