簡介：

0-1背包問題是經典的組合優化問題：給定一組物品（每個物品有重量和價值），在背包容量限制下選擇物品裝入背包，要求總價值最大化且每個物品不可重復選取。

動態規劃核心思想

通過構建二維狀態表dp[i][j]，記錄前i個物品在容量j時的最大價值，通過狀態轉移方程逐步推導最優解，避免重復計算子問題。

---

問題建模與參數定義

static final Integer N = 4;       // 物品數量
static final Integer W = 5;       // 背包容量
Integer[] w = {0,1,2,3,4};        // 物品重量數組（索引0占位）
Integer[] v = {0,2,4,5,6};        // 物品價值數組
private Integer[][] table = new Integer[N+1][W+1]; // DP狀態表

---

代碼執行全流程解析

1. 初始化階段 init()

for(int i=0;i<=N;i++) {for(int j=0;j<=W;j++) {table[i][j]=0;}
}

🔍 執行過程：

1. 創建(N+1)行×(W+1)列的二維數組
2. 初始化邊界條件：
   • table[0][j] = 0（無物品可裝）
   • table[i][0] = 0（無容量可用）

┌───────────────┐
│  Start Init  │
└───────┬───────┘│
┌───────▼───────┐
│ i=0 to N     │
├───────┬───────┤
│ j=0 to W     │
├───────▼───────┤
│ table[i][j]=0 │
└───────┬───────┘│
┌───────▼───────┐
│ End Init      │
└───────────────┘

---

2. 動態規劃核心 dynamics()

for(int i=1;i<=N;i++) {          // 物品維度for(int j=1;j<=W;j++) {      // 容量維度// 不選當前物品table[i][j] = table[i-1][j]; // 選當前物品（需容量足夠）if(j >= w[i]) {table[i][j] = max(table[i][j], table[i-1][j-w[i]] + v[i]);}}
}

📊 狀態轉移矩陣演變：

迭代過程示例（i=2時）：容量 j | 0 1 2 3 4 5
i=0     | 0 0 0 0 0 0
i=1     | 0 2 2 2 2 2 
i=2     | 0 2 max(2,2+4)=6 ...

---

完整流程圖與時序圖

系統級流程圖

時序圖

---

復雜度深度分析

時間復雜度：

• 雙重循環：O(N*W) = 4×5 = 20次核心計算
• 計算過程：

Σ(i=1→4) Σ(j=1→5) [1次比較 + 1次查詢] = 4×5×2 = 40次操作

空間復雜度：

• 二維數組存儲：O(N*W) = 5×6 = 30個存儲單元
• 空間消耗分解：

基礎類型Integer × 30 = 30×4 bytes = 120 bytes

---

完整代碼

public class Knapsack {/** 假設有背包中可以最多可以裝4個產品；背包承受的最大容量為5，求該背包最大的價值為多少* N：為物品數量* W：為背包容量* w[]:表示每一個產品容量* v[]:表示每一個產品的價值** */static final Integer N =4;static final Integer W= 5;Integer[] w =new Integer[]{0,1,2,3,4};Integer[] v= new  Integer[]{0,2,4,5,6};private Integer[][] table = new  Integer[N+1][W+1];void  init(){for(int i=0;i<=N;i++){for(int j=0;j<=W;j++){table[i][j]=0;}}}void print(){for(int i=0;i<=N;i++){for(int j=0;j<=W;j++){System.out.print(table[i][j]+"   ");}System.out.println();}}void dynamics(){for(int i=1;i<=N;i++){for(int j=1;j<=W;j++){table[i][j]=table[i-1][j]; // 不選第i個物品if(j>=w[i]){// 選第i個物品table[i][j]=max(table[i][j],table[i-1][j-w[i]]+v[i]);}}}}// 判斷大小的方法Integer max(Integer value1,Integer value2){return value1>value2?value1:value2;}public static void main(String[] args) {Knapsack k=new Knapsack();k.init();k.dynamics();k.print();}
}

結果截圖：

擴展解法對比

1. 回溯法（決策樹實現）

int backtrack(int i, int currentW, int currentV) {if(i > N) return currentV;if(currentW + w[i] > W) {return backtrack(i+1, currentW, currentV);}return max(backtrack(i+1, currentW, currentV),backtrack(i+1, currentW + w[i], currentV + v[i]));
}

?? 問題規模達20時計算量超百萬次

2. 空間優化DP（滾動數組）

int[] dp = new int[W+1];
for(int i=1; i<=N; i++){for(int j=W; j>=w[i]; j--){ // 逆序更新dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);}
}

🔧 優勢：空間復雜度降為O(W) = 6 units

3. 分支限界法（優先隊列實現）

from queue import PriorityQueueclass Node:def __init__(self, level, weight, value, bound):self.level = levelself.weight = weightself.value = valueself.bound = bounddef bound(node):# 計算剩余物品的最大可能價值...

---

算法選擇策略

方法	適用場景	時間復雜度	空間復雜度
標準動態規劃	中小規模精確計算	O(N*W)	O(N*W)
空間優化DP	大規模數據處理	O(N*W)	O(W)
回溯法	物品數<20	O(2^N)	O(N)
分支限界法	需要快速近似解	O(2^N)	O(2^N)

---

完整代碼執行結果

0   0   0   0   0   0   
0   2   2   2   2   2   
0   2   4   6   6   6   
0   2   4   6   7   9   
0   2   4   6   7   9   

最終最大價值為 9，通過物品選擇（2+3號物品：重量2+3=5，價值4+5=9）實現

---