作者：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时，价值为04️⃣ 遍历顺序
二维版本：
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：处理变种
| 变种类型 | 调整方法 |
|---|---|
| 恰好装满 | 初始化dp[0]=0，其余为-Infinity |
| 至少装满 | 同上 |
| 求方案数 | dp[v] += dp[v-w] |
| 求是否可行 | `dp[v] = dp[v] |
📚 经典例题
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 背包 | 完全背包 |
|---|---|---|
| 物品使用次数 | 每个物品最多选1次 | 每个物品可选无限次 |
| 容量遍历顺序 | 倒序（v: V → w） | 正序（v: w → V） |
| 状态转移 | dp[v] = max(dp[v], dp[v-w]+val) | 相同 |
| 典型问题 | 分割等和子集 | 零钱兑换 |
💡 记忆技巧
口诀：
0-1 背包倒着来，完全背包正着排
本质理解：
- 倒序 = 保证
dp[v-w]是上一轮的旧值 = 物品只用一次 - 正序 = 允许
dp[v-w]是本轮的新值 = 物品可重复用
📖 延伸阅读
- 多重背包：每个物品有数量限制（介于 0-1 和完全之间）
- 分组背包：物品分组，每组只能选一个
- 树形背包：在树结构上做背包DP
- 背包求方案数：不是求最大值，而是求有多少种方案
✅ 总结
0-1 背包的核心：
- 状态定义：
dp[v]= 容量为v时的最大价值 - 状态转移：选或不选当前物品
- 关键技巧：一维优化时必须倒序遍历
- 本质理解：倒序保证每个物品只用一次
掌握这个模板后，90% 的背包问题都能解决！
如果觉得有帮助，欢迎点赞收藏！
有疑问欢迎评论区讨论 😊
