## 背包問題

---

### 背包問題是啥

背包問題是**動態規劃 (Dynamic Programming, DP)** 最經典的問題之一。它的核心思想是通過將問題拆解成子問題，慢慢一步一步解完他們。


#### 背包問題在幹嘛?
- 有一個容量為 `W` 的背包。
- 有 `n` 件物品，每件物品有兩個屬性：
- **重量 (`weight[i]`)**
- **價值 (`value[i]`)**
(這裡會把`weight`和`value`當成陣列分別存每個物品的重量和價值)
- **目標**：讓放進背包的物品總重量不超過 `W`，且總價值最大化。
- **限制**：每個物品最多只能選擇一次（這就是所謂的「01 背包問題」），每個背包問題都會有些不一樣的限制，這裡先用最常見也最基礎的01背包做講解

---

### 二維 DP 背包問題 (01 背包)

#### 狀態定義
我們用一個**二維陣列 `dp[i][j]`** 來表示：
- `dp[i][j]`：表示考慮前 `i` 件物品，且背包容量為 `j` 時，所能達到的最大價值。

換句話說：
- 如果我們只考慮前 `i` 件物品，並且背包容量為 `j`，那麼可以裝進背包的最大價值是多少。

---

#### 狀態轉移方程式


dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);

這個公式分成兩部分：
1. **不選擇第 `i` 件物品**：
- 如果不選擇第 `i` 件物品，那麼最大價值等於「只考慮前 `i-1` 件物品，且剩餘背包容量為 `j` 時的最大價值」。
- 對應的狀態是 `dp[i-1][j]`。

2. **選擇第 `i` 件物品**：
- 如果選擇第 `i` 件物品，那麼最大價值等於「只考慮前 `i-1` 件物品，且背包剩餘容量為 `j - weight[i]` 時的最大價值」，再加上第 `i` 件物品的價值 `value[i]`。
- 對應的狀態是 `dp[i-1][j-weight[i]] + value[i]`。

3. **取兩者的較大值**：
- 我們肯定是希望最後的價值是最大的，所以取 `max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])`。

---

#### 初始條件
1. **背包容量為 0 時** (`j = 0`)：
- 沒東西放，你當然一點價值都沒有(嗯? 所以 `dp[i][0] = 0`。

2. **沒有物品可選時** (`i = 0`)：
- 無論背包容量多大，你沒東西拿，還是一樣一點價值都沒有(嗯? 所以 `dp[0][j] = 0`。

---

## 每次進入 `dp[i][j]` 判斷時他到底會怎麼走：

#### 假設當前 `i = 3`，`j = 5`，物品 `3` 的重量為 `3`，價值為 `4`，我們檢查 `dp[3][5]`。

#### 1. **檢查能否選擇物品 `3`**：
- 條件：`j >= weight[3]`。
- 如果 `j = 5` 且 `weight[3] = 3`，滿足條件，可以選擇物品。

#### 2. **計算不選擇物品 `3` 的情況**：
- 最大價值為「只考慮前 `2` 件物品，且容量為 `5` 時的最大價值」。
- 對應：`dp[2][5]`。

#### 3. **計算選擇物品 `3` 的情況**：
- 假設選擇物品 `3`，需要考慮剩餘容量 `j - weight[3] = 5 - 3 = 2`。
- 最大價值為「前 `2` 件物品在容量 `2` 時的最大價值」加上物品 `3` 的價值 `4`。
- 對應：`dp[2][2] + value[3]`。

#### 4. **取兩者的最大值**：
- 比較 `dp[2][5]` 和 `dp[2][2] + value[3]`，取較大值作為 `dp[3][5]`。

---

## 全過程的逐步演示：

假設有以下物品：
| 物品編號 | 重量 (`weight`) | 價值 (`value`) |
|----------|----------------|----------------|
| 1 | 2 | 3 |
| 2 | 1 | 2 |
| 3 | 3 | 4 |
| 4 | 2 | 2 |

背包容量 `W = 5`。

初始 `dp` 陣列為：

dp[i][j] = 0 (所有 i 和 j 都初始化為 0)

---

### 第 1 件物品 (`weight[1] = 2`, `value[1] = 3`)：
- 只更新容量 `j >= 2` 的情況，公式為：

  dp[1][j] = max(dp[0][j], dp[0][j-2] + 3);

| 容量 (`j`) | 更新公式 | 結果 |
|------------|--------------------------|------|
| `j = 0` | 無法放入，`dp[1][0] = 0` | 0 |
| `j = 1` | 無法放入，`dp[1][1] = 0` | 0 |
| `j = 2` | `max(0, 0 + 3)` | 3 |
| `j = 3` | `max(0, 0 + 3)` | 3 |
| `j = 4` | `max(0, 0 + 3)` | 3 |
| `j = 5` | `max(0, 0 + 3)` | 3 |

---

### 第 2 件物品 (`weight[2] = 1`, `value[2] = 2`)：
- 只更新容量 `j >= 1` 的情況，公式為：

  dp[2][j] = max(dp[1][j], dp[1][j-1] + 2);

| 容量 (`j`) | 更新公式 | 結果 |
|------------|--------------------------|------|
| `j = 0` | 無法放入，`dp[2][0] = 0` | 0 |
| `j = 1` | `max(0, 0 + 2)` | 2 |
| `j = 2` | `max(3, 0 + 2)` | 3 |
| `j = 3` | `max(3, 3 + 2)` | 5 |
| `j = 4` | `max(3, 3 + 2)` | 5 |
| `j = 5` | `max(3, 3 + 2)` | 5 |

---

### 第 3 件物品 (`weight[3] = 3`, `value[3] = 4`)：
- 只更新容量 `j >= 3` 的情況，公式為：

  dp[3][j] = max(dp[2][j], dp[2][j-3] + 4);

| 容量 (`j`) | 更新公式 | 結果 |
|------------|--------------------------|------|
| `j = 0` | 無法放入，`dp[3][0] = 0` | 0 |
| `j = 1` | 無法放入，`dp[3][1] = 2` | 2 |
| `j = 2` | 無法放入，`dp[3][2] = 3` | 3 |
| `j = 3` | `max(5, 0 + 4)` | 5 |
| `j = 4` | `max(5, 2 + 4)` | 6 |
| `j = 5` | `max(5, 3 + 4)` | 7 |

---

### 最終結果：
當考慮所有物品且背包容量為 `5` 時，`dp[4][5]` 的最大價值為 `7`。

---

## 所以?：
1. **每次進入 `dp[i][j]` 時，我們會檢查是否能選擇當前物品**，並分別計算選擇與不選擇的情況。
2. **狀態轉移公式的核心是取兩者的最大值**，這保證了我們逐步構建最優解。
3. **通過動態規劃，我們有效地解決了重疊子問題，並利用最優子結構性質找到整體最優解**。

#### 實現範例（完整程式碼）

假設有以下物品：
- 物品 1：重量 2，價值 3
- 物品 2：重量 1，價值 2
- 物品 3：重量 3，價值 4
- 物品 4：重量 2，價值 2

背包容量為 `W = 5`。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int W = 5;
    vector<int> weight = {2, 1, 3, 2};
    vector<int> value = {3, 2, 4, 2};
    int n = weight.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= W; j++){
            if (j >= weight[i-1]){
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1]);
            } 
			else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << "最大價值: " << dp[n][W] << '\n';

}

---

### 為什麼這樣做可以解決背包問題？
1. **問題拆解**：
- 這樣解可以將原問題拆解成「是否選擇當前物品」的兩種情況，這樣可以逐步縮小問題規模，並用子問題的解構建出原問題的解。

2. **最優子結構**：
- 每個子問題的最優解可以用來構建更大的問題的最優解。
- 例如，`dp[i][j]` 的最優解是由 `dp[i-1][j]` 和 `dp[i-1][j-weight[i]] + value[i]` 的最優解組成的。

3. **那又為何使用dp?**：
- 在計算過程中，許多子問題會被重複計算。
- 這很顯然就是dp的適用情況了，用陣列把結果存下來避免過多非必要運算

---

### 壓縮到一維 DP
#### 核心邏輯
仔細思考會發現，背包用二維陣列存其實很浪費空間，陣列裡的`i`其實不太必要，我們可以嘗試刪掉後改成一維陣列，可以有效減少空間浪費。

#### 狀態定義
- **`dp[j]`**：表示背包容量為 `j` 時的最大價值。

#### 狀態轉移方程式
轉移方程式與二維 DP 相同：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

#### 小重點：遍歷順序
- 必須從右向左更新 `dp[j]`。
- **為什麼？**
- 如果從左向右更新，會導致當前面的結果影響到後面的計算，然後開始一步錯步步錯，跟我的人生一樣拿到WA

---

#### 一維 DP 實現範例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int W = 5;
    vector<int> weight = {2, 1, 3, 2};
    vector<int> value = {3, 2, 4, 2};
    int n = weight.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++){
        for (int j = W; j >= weight[i]; j--){
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << "最大價值: " << dp[W] << '\n';
}

---

### 完全背包問題 (無限次選擇物品)

#### 問題描述

每種物品可以被選擇無限次，但總重量不能超過背包容量 `W`。

---

#### 狀態轉移方程式
與 01 背包的公式類似，但是每種物品可以被多次選擇，因此需要改變遍歷順序：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

#### 小重點：遍歷順序
- 必須從左向右更新 `dp[j]`，以確保每個物品可以被重複使用。
- **為什麼？**
- 如果從右向左遍歷，會錯過重複選擇同一物品的機會。

---

#### 完全背包實現範例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int W = 5;
    vector<int> weight = {2, 1, 3, 2};
    vector<int> value = {3, 2, 4, 2};
    int n = weight.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++){
        for (int j = weight[i]; j <= W; j++){
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << "最大價值: " << dp[W] << '\n';
}

---

### 小結

1. **二維 DP** 是理解背包問題的基礎方法，有助於清晰地看到每層的狀態轉移。
2. **一維 DP** 是對空間的優化，適合處理大規模問題。
3. **完全背包** 是背包問題的重要變形，通過改變遍歷順序來實現無限次選擇。