一、問題描述

給定一個容量為 W 的背包和 n 個物品。每個物品有一個重量 w[i] 和價值 v[i]。每個物品只能選或不選（即“0-1”），求在不超過背包容量的前提下，所能獲得的最大總價值。

輸入：

• 背包容量 W（int）
• 物品數量 n（int）
• 每個物品的重量 w[i]（int[]）
• 每個物品的價值 v[i]（int[]）

輸出：

• 最大總價值（int）

---

二、建模分析

定義 dp[i][j] 表示：前 i 個物品中選取若干個，放入容量為 j 的背包中所能獲得的最大價值。

狀態轉移方程：

• 如果不選第 i 個物品：

  dp[i][j] = dp[i - 1][j]
  

• 如果選第 i 個物品（前提是 j >= w[i]）：

  dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
  

初始條件：dp[0][*] = 0（0 個物品時，無論容量多少，價值都是 0）

最終答案：dp[n][W]

---

三、Java 實現（二維 DP）

public class Knapsack01 {public static int knapsack(int[] weights, int[] values, int W) {int n = weights.length;int[][] dp = new int[n + 1][W + 1];for (int i = 1; i <= n; i++) {int wi = weights[i - 1];int vi = values[i - 1];for (int j = 0; j <= W; j++) {if (j < wi) {dp[i][j] = dp[i - 1][j]; // 裝不下} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wi] + vi);}}}return dp[n][W];}public static void main(String[] args) {int[] weights = {2, 1, 3};int[] values = {4, 2, 3};int W = 4;System.out.println(knapsack(weights, values, W)); // 輸出最大價值}
}

---

四、空間優化（滾動數組）

二維數組空間復雜度為 O(nW)，可以用一維數組降為 O(W)：

public class Knapsack01Optimized {public static int knapsack(int[] weights, int[] values, int W) {int n = weights.length;int[] dp = new int[W + 1];for (int i = 0; i < n; i++) {for (int j = W; j >= weights[i]; j--) {dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);}}return dp[W];}
}

?? **注意：**必須倒序遍歷 j，否則會重復使用同一物品，變成“完全背包”問題。

---

五、實際應用場景

• 項目預算分配（有限資源選擇最優組合）
• 云資源調度（選擇若干任務部署到有限資源池）
• 投資組合選擇（限定資金下選擇最大收益）
• 嵌入式設備資源優化（內存/能耗限制下選擇模塊）

---

六、變種問題（可擴展）

問題類型	描述	變化點
完全背包	每個物品可以選多次	內層循環從小到大
多重背包	每個物品有限個數	轉換成多個“0-1背包項”
多維背包	背包有多個限制條件（如體積）	dp[i][j][k]... 多維數組
分組背包	多個物品組，每組最多選一個	分組循環 + DP