0-1 背包问题完全指南：从理解到模板

作者：bjmayor
适用人群：有编程基础，想彻底理解动态规划的学习者

📌 问题定义

0-1 背包问题：

• 有一个容量为V的背包
• 有n个物品，每个物品有：
  • 重量weight[i]
  • 价值value[i]
• 每个物品只能选择一次（0 或 1）
• 求：在不超过背包容量的前提下，能获得的最大总价值

示例：

背包容量 V = 5 物品列表： 物品0: weight=2, value=3 物品1: weight=3, value=4 物品2: weight=4, value=5 最优方案：选物品0和物品1，总重量=5，总价值=7

🧠 核心思路：动态规划

1️⃣ 状态定义

二维DP：

dp[i][v] = 前 i 个物品，背包容量为 v 时的最大价值

一维DP（空间优化后）：

dp[v] = 背包容量为 v 时的最大价值

2️⃣ 状态转移方程

对于第i个物品（重量w，价值val），有两种选择：

不选物品 i：dp[i][v] = dp[i-1][v] 选物品 i： dp[i][v] = dp[i-1][v-w] + val (前提: v >= w) 状态转移： dp[i][v] = max(dp[i-1][v], dp[i-1][v-w] + val)

核心理解：

• dp[i-1][v]：不选当前物品，价值继承上一层
• dp[i-1][v-w] + val：选当前物品，需要预留w的空间，价值增加val

3️⃣ 初始化

dp[0][...]=0// 没有物品时，价值为0dp[...][0]=0// 容量为0时，价值为0

4️⃣ 遍历顺序

二维版本：

for(leti=0;i<n;i++){// 枚举物品for(letv=0;v<=V;v++){// 枚举容量（正序或倒序都可以）// 状态转移}}

一维版本（关键）：

for(leti=0;i<n;i++){// 枚举物品for(letv=V;v>=weight[i];v--){// ⚠️ 必须倒序！// 状态转移}}

⚠️ 为什么一维版本必须倒序遍历？

这是 0-1 背包最容易出错的地方！

❌ 正序遍历的问题

for(letv=weight[i];v<=V;v++){// 从小到大dp[v]=Math.max(dp[v],dp[v-weight[i]]+value[i]);}

会发生什么？

假设weight[i] = 2, value[i] = 3：

初始: dp = [0, 0, 0, 0, 0, 0] v = 2: dp[2] = max(0, dp[0] + 3) = 3 dp = [0, 0, 3, 0, 0, 0] ← 物品 i 被使用1次 v = 4: dp[4] = max(0, dp[2] + 3) = 6 dp = [0, 0, 3, 0, 6, 0] ← 物品 i 被使用2次！ ↑ 这里用的是更新后的 dp[2]=3

问题：同一个物品被重复使用了！

✅ 倒序遍历的正确性

for(letv=V;v>=weight[i];v--){// 从大到小dp[v]=Math.max(dp[v],dp[v-weight[i]]+value[i]);}

执行过程：

初始: dp = [0, 0, 0, 0, 0, 0] v = 4: dp[4] = max(0, dp[2] + 3) = 3 dp = [0, 0, 0, 0, 3, 0] ← 用的是旧的 dp[2]=0 v = 2: dp[2] = max(0, dp[0] + 3) = 3 dp = [0, 0, 3, 0, 3, 0] ← 现在才更新 dp[2]

原理：

• 倒序遍历时，dp[v]依赖的dp[v-w]一定是上一轮的旧值
• 保证了每个物品只被使用一次

记忆口诀：

0-1 背包倒序遍历，完全背包正序遍历

📝 标准代码模板

模板1：二维DP（易理解）

functionknapsack01_2D(weights,values,capacity){constn=weights.length;// dp[i][v] = 前i个物品，容量为v时的最大价值constdp=Array(n+1).fill(0).map(()=>Array(capacity+1).fill(0));// 枚举物品for(leti=0;i<n;i++){constw=weights[i];constval=values[i];// 枚举容量for(letv=0;v<=capacity;v++){// 不选物品 idp[i+1][v]=dp[i][v];// 选物品 i（如果放得下）if(v>=w){dp[i+1][v]=Math.max(dp[i+1][v],dp[i][v-w]+val);}}}returndp[n][capacity];}

模板2：一维DP（空间优化，推荐）

functionknapsack01(weights,values,capacity){constn=weights.length;constdp=Array(capacity+1).fill(0);// 枚举物品for(leti=0;i<n;i++){constw=weights[i];constval=values[i];// ⚠️ 倒序枚举容量（从大到小）for(letv=capacity;v>=w;v--){dp[v]=Math.max(dp[v],// 不选物品 idp[v-w]+val// 选物品 i);}}returndp[capacity];}

模板3：打印具体方案（选了哪些物品）

functionknapsack01WithPath(weights,values,capacity){constn=weights.length;constdp=Array(n+1).fill(0).map(()=>Array(capacity+1).fill(0));// 填表for(leti=0;i<n;i++){for(letv=0;v<=capacity;v++){dp[i+1][v]=dp[i][v];if(v>=weights[i]){dp[i+1][v]=Math.max(dp[i+1][v],dp[i][v-weights[i]]+values[i]);}}}// 回溯路径constselected=[];letv=capacity;for(leti=n-1;i>=0;i--){// 如果这一层和上一层不同，说明选了物品 iif(dp[i+1][v]!==dp[i][v]){selected.push(i);v-=weights[i];}}return{maxValue:dp[n][capacity],items:selected.reverse()};}

🎯 解题套路总结

步骤1：识别是否为 0-1 背包

特征：

• ✅ 有容量限制
• ✅ 有价值需要最大化
• ✅每个物品只能选一次

变种识别：

• “分割等和子集” → 目标和背包
• “最后一块石头的重量II” → 最小差值背包
• “目标和” → 组合数背包

步骤2：套用模板

// 1. 定义 dp 数组constdp=Array(capacity+1).fill(0);// 2. 枚举物品for(leti=0;i<n;i++){// 3. ⚠️ 倒序枚举容量for(letv=capacity;v>=weight[i];v--){// 4. 状态转移dp[v]=Math.max(dp[v],dp[v-weight[i]]+value[i]);}}// 5. 返回结果returndp[capacity];

步骤3：处理变种

📚 经典例题

LeetCode 416. 分割等和子集

问题转换：

• 背包容量 =sum / 2
• 物品重量 = 数组元素
• 物品价值 = 数组元素
• 目标：是否存在方案使得总价值 =sum / 2

functioncanPartition(nums){constsum=nums.reduce((a,b)=>a+b,0);if(sum%2!==0)returnfalse;consttarget=sum/2;constdp=Array(target+1).fill(false);dp[0]=true;// 容量为0时，一个都不选，方案存在for(letnumofnums){for(letv=target;v>=num;v--){dp[v]=dp[v]||dp[v-num];// ⚠️ 求是否可行}}returndp[target];}

LeetCode 474. 一和零

二维背包：

• 两个容量限制：m个 0，n个 1
• dp[i][j]= 最多有i个 0 和j个 1 时的最大子集数量

functionfindMaxForm(strs,m,n){constdp=Array(m+1).fill(0).map(()=>Array(n+1).fill(0));for(letstrofstrs){constzeros=str.split('0').length-1;constones=str.length-zeros;// ⚠️ 两个维度都要倒序for(leti=m;i>=zeros;i--){for(letj=n;j>=ones;j--){dp[i][j]=Math.max(dp[i][j],dp[i-zeros][j-ones]+1);}}}returndp[m][n];}

⚡ 常见错误

❌ 错误1：容量正序遍历

for(letv=weight[i];v<=capacity;v++){// ❌dp[v]=Math.max(dp[v],dp[v-weight[i]]+value[i]);}

后果：物品被重复使用

❌ 错误2：初始化错误

// 如果要求"恰好装满"constdp=Array(capacity+1).fill(0);// ❌ 应该初始化为 -Infinitydp[0]=0;// 只有容量0时值为0

❌ 错误3：混淆重量和价值

dp[v]=Math.max(dp[v],dp[v-value[i]]+weight[i]);// ❌// ↑ 应该是 weight[i] ↑ 应该是 value[i]

🔄 0-1 背包 vs 完全背包

💡 记忆技巧

口诀：

0-1 背包倒着来，完全背包正着排

本质理解：

• 倒序 = 保证dp[v-w]是上一轮的旧值 = 物品只用一次
• 正序 = 允许dp[v-w]是本轮的新值 = 物品可重复用

📖 延伸阅读

1. 多重背包：每个物品有数量限制（介于 0-1 和完全之间）
2. 分组背包：物品分组，每组只能选一个
3. 树形背包：在树结构上做背包DP
4. 背包求方案数：不是求最大值，而是求有多少种方案

✅ 总结

0-1 背包的核心：

1. 状态定义：dp[v]= 容量为v时的最大价值
2. 状态转移：选或不选当前物品
3. 关键技巧：一维优化时必须倒序遍历
4. 本质理解：倒序保证每个物品只用一次

掌握这个模板后，90% 的背包问题都能解决！

如果觉得有帮助，欢迎点赞收藏！
有疑问欢迎评论区讨论 😊