背包好好玩，所以把他分出來講。
寫背包問題，聽[你的背包](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)$
Sign in with Wallet
Connect another wallet