简介：
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; } }
🔍 执行过程：
- 创建(N+1)行×(W+1)列的二维数组
- 初始化边界条件：
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] ); } } }
核心代码分点解析
1. 外层循环：物品遍历
for (int i = 1; i <= N; i++)
- 作用：逐个考虑是否将第
i个物品加入背包 - 范围：
1 ≤ i ≤ N（N=4个物品） - 物理意义：构建包含前
i个物品的最优解 - 示例：当
i=3时，表示正在处理物品3（重量3，价值5）
2. 内层循环：容量遍历
for (int j = 1; j <= W; j++)
- 作用：计算不同容量下的最大价值
- 范围：
1 ≤ j ≤ W（W=5容量） - 物理意义：模拟背包容量从1到5的逐步填充过程
- 示例：当
j=5时，计算背包满容量时的最优解
3. 默认决策：不选当前物品
table[i][j] = table[i-1][j]
- 逻辑：直接继承前
i-1个物品在容量j时的最优解 - 数学表达：
dp[i][j] = dp[i-1][j] - 示例：当不选物品3时，
table[3][5] = table[2][5] = 6
4. 容量判断条件
if (j >= w[i])
- 作用：验证当前容量能否容纳物品
i - 数学意义：判断
j ≥ w[i]是否成立 - 边界案例：
w[i]=3时，j=2→ 不满足j=5→ 满足（5 ≥ 3）
5. 选择物品的决策
table[i-1][j - w[i]] + v[i]
- 分步解析：
j - w[i]：放入物品后的剩余容量table[i-1][...]：前i-1个物品在剩余容量的最优解+ v[i]：叠加当前物品价值
- 示例：
当i=3（w=3, v=5），j=5时：j-w[i] = 5-3 = 2→table[2][2] = 4→4 + 5 = 9
6. 最优决策比较
max(table[i][j], ...)
- 比较对象：
table[i][j]：不选当前物品的价值table[i-1][j-w[i]] + v[i]：选择当前物品的总价值
- 决策树示例（
i=3, j=5）：
max(6, 9) → 取9
动态过程示例（i=3, w[i]=3, v[i]=5）
容量j |
计算过程 |
结果值 |
3 |
max(6, table[2][0]+5=5) → 6 |
6 |
4 |
max(6, table[2][1]+5=2+5=7) → 7 |
7 |
5 |
max(6, table[2][2]+5=4+5=9) → 9 |
9 |
最终table[4][5] = 9即为最大价值。
📊 状态转移矩阵演变：
迭代过程示例（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 PriorityQueue class Node: def __init__(self, level, weight, value, bound): self.level = level self.weight = weight self.value = value self.bound = bound def 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）实现
工程实践建议
- 物品索引处理：Java数组从0开始，建议保持统一索引体系
- 大数据优化：当W>10^6时，需采用贪心近似算法
- 价值类型扩展：可改造为浮点数处理分数背包问题
- 路径回溯实现：增加布尔矩阵记录选择状态，用于重构最优解
