前言

動態規劃背包問題是一類經典的優化問題，涉及到選擇物品以最大化某個目標值（通常是價值或利潤），同時受到某種約束（如重量、體積或時間）。背包問題可以分為多種類型，例如0-1背包問題、完全背包問題、多重背包問題等。在0-1背包問題中，每種物品只有一個，可以選擇放或不放；在完全背包問題中，每種物品有無限個，可以選擇放任意個；在多重背包問題中，每種物品有有限個，可以選擇放任意個但不能超過給定的數量。

?解決背包問題的關鍵是定義狀態并寫出狀態轉移方程。通常，我們會定義一個二維數組dp，其中dp[i][j]表示在前i個物品中選擇一些物品放入容量為j的背包中所能獲得的最大價值。然后，我們可以通過狀態轉移方程來逐步計算dp數組的值。

01背包：

01背包問題是背包問題中的一種基礎且常見的類型。在這個問題中，每種物品都只有一件，可以選擇放入背包或者不放入背包。01背包問題的目標是選擇一些物品放入背包，使得背包中物品的總價值最大，同時不超過背包的容量限制。

關鍵點

1. 物品數量限制：每種物品只有一個，不能重復選擇。
2. 價值最大化：目標是最大化背包中物品的總價值。
3. 容量限制：背包有一個固定的容量，選擇的物品總體積不能超過這個容量。

動態規劃解法

對于01背包問題，可以使用動態規劃來求解。動態規劃的核心是定義狀態和寫出狀態轉移方程。

二維數組：

1. 定義狀態：定義dp[i][j]為考慮前i個物品，在容量為j的背包中能夠獲得的最大價值。
2. 狀態轉移方程：對于第i個物品，有兩種選擇：放入背包或不放入背包。如果放入背包，則背包的剩余容量為j - weight[i]，此時的最大價值為dp[i-1][j-weight[i]] + value[i]；如果不放入背包，則最大價值為dp[i-1][j]。因此，狀態轉移方程為：

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

1. 初始化：通常將dp[0][j]初始化為0，表示不放入任何物品時的最大價值為0。同時，dp[i][0]也應初始化為0，表示背包容量為0時的最大價值為0。
2. 求解：按照狀態轉移方程逐步計算dp數組的值，最終dp[n][W]即為所求的最大價值，其中n是物品的數量，W是背包的容量。

一維數組：

在01背包問題中，由于每種物品只有一個，我們不需要考慮重復選擇同一物品的情況。這使得我們可以使用一維數組來減少空間復雜度，而不是傳統的二維數組。

1. 定義狀態：
   • 使用一維數組dp，其中dp[j]表示在容量為j的背包中能夠獲得的最大價值。
2. 狀態轉移方程：
   • 對于每個物品i，我們只需要考慮是否將其放入背包。如果放入，則背包的剩余容量為j - weights[i]，此時的最大價值為dp[j - weights[i]] + values[i]。
   • 因此，狀態轉移方程為：dp[j] = max(dp[j], dp[j - weights[i]] + values[i])。
3. 初始化：
   • dp[0]應該初始化為0，因為當背包容量為0時，無法放入任何物品，所以最大價值為0。
   • 對于j > 0，dp[j]的初始值依賴于問題的定義。在標準的01背包問題中，通常可以初始化為一個較小的負數，因為不放入任何物品時的價值應該是0。
4. 遍歷順序：
   • 外層循環遍歷物品，內層循環遍歷背包容量。對于每個物品，從背包容量W開始向前遍歷到該物品的重量weights[i]，確保每個物品只被考慮一次。
5. 求解：
   • 在完成所有狀態轉移后，dp[W]將包含最大價值，其中W是背包的總容量。
6. 空間復雜度：
   • 使用一維數組實現，空間復雜度為O(W)，其中W是背包的容量，與物品的數量n無關。
7. 注意事項：
   • 確保在遍歷背包容量時從大到小進行，以避免重復計算同一個物品的價值。
   • 這種實現方式利用了01背包問題的特性，即每種物品只有一個，不允許重復選擇。

總的來說，一維數組實現01背包問題通過巧妙地利用狀態轉移方程和遍歷順序，減少了空間復雜度，同時保持了時間復雜度為O(nW)，其中n是物品的數量，W是背包的容量。

優化

在實際應用中，01背包問題可以通過一些優化手段來減少空間復雜度。例如，可以使用滾動數組來只保存當前狀態和前一個狀態的信息，從而將空間復雜度從O(nW)降低到O(W)。此外，還可以通過一些數學性質來進一步優化算法。

完全背包：

完全背包問題是背包問題的一種變體，它與01背包問題的主要區別在于每種物品有無限個，即可以選擇放入背包0個、1個、2個...等任意個。完全背包問題的目標同樣是選擇一些物品放入背包，使得背包中物品的總價值最大，同時不超過背包的容量限制。

關鍵點

1. 物品數量無限制：每種物品有無限個，可以重復選擇。
2. 價值最大化：目標是最大化背包中物品的總價值。
3. 容量限制：背包有一個固定的容量，選擇的物品總體積不能超過這個容量。

動態規劃解法

對于完全背包問題，也可以使用動態規劃來求解。與01背包問題相比，完全背包問題的狀態轉移方程稍有不同。

二維數組：

1. 定義狀態：同樣定義dp[i][j]為考慮前i個物品，在容量為j的背包中能夠獲得的最大價值。
2. 狀態轉移方程：對于第i個物品，由于數量無限制，可以選擇放入0個、1個、2個...等任意個。因此，對于每種可能的數量k（0 ≤ k ≤ j / weight[i]），可以選擇放入k個第i個物品，此時背包的剩余容量為j - k * weight[i]，最大價值為dp[i-1][j-k*weight[i]] + k*value[i]。取所有可能的k中的最大值作為dp[i][j]的值。即：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i], dp[i-1][j-2*weight[i]] + 2*value[i], ..., dp[i-1][j-k*weight[i]] + k*value[i])。在實際實現中，可以通過循環來遍歷所有可能的k值。
3. 初始化：與01背包問題相同，將dp[0][j]初始化為0，表示不放入任何物品時的最大價值為0。同時，dp[i][0]也應初始化為0，表示背包容量為0時的最大價值為0。
4. 求解：按照狀態轉移方程逐步計算dp數組的值，最終dp[n][W]即為所求的最大價值，其中n是物品的數量，W是背包的容量。

一維數組：

1. 定義：一個一維數組dp，其中dp[j]表示在容量為j的背包中能夠獲得的最大價值。
2. 狀態轉移方程如下：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
3. 這個方程的含義是，對于每個物品i，我們考慮放入0個、1個、2個...等任意個，直到背包容量不足以容納更多的該物品。對于每個可能的數量k（0 ≤ k ≤ j / weight[i]），我們計算放入k個物品i后的總價值，并更新dp[j]為所有可能情況中的最大值。
4. 最終，dp[W]就是所求的最大價值，其中W是背包的容量。

需要注意的是，這里并沒有直接計算背包的體積，因為背包的體積是固定的，我們關注的是如何在不超過這個體積限制的情況下最大化價值。物品的體積是用來判斷是否可以將物品放入背包的約束條件。

優化

對于完全背包問題，一種常見的優化方法是使用一維數組來減少空間復雜度。由于每種物品可以無限次選擇，因此在遍歷物品時，可以從大到小遍歷，保證每個物品只被添加一次。這樣可以將空間復雜度從O(nW)降低到O(W)。此外，還可以利用一些數學性質來進一步優化算法，例如利用物品的單調性來減少不必要的計算。總之，完全背包問題是背包問題的一種變體，其特點在于每種物品有無限個。通過動態規劃的方法可以有效地求解完全背包問題，并根據具體問題的特點進行相應的優化。