动态规划算法深度解析：0-1背包问题（含完整流程）

简介：

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）实现

---