知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 12 - 0-1 背包问题 ## 题目 有 n 个物品,每个物品有重量 w[i] 和价值 v[i]。背包容量为 W,每个物品只能选一次,求能装下的最大价值。 ``` 物品: 重量 价值 物品0: 1 15 物品1: 3 20 物品2: 4 30 背包容量 W = 4 最大价值 = 35(选物品0 + 物品1:重量 1+3=4,价值 15+20=35) ``` ## 先搞清楚:0-1 背包 vs 完全背包 ``` 0-1 背包:每个物品只能选一次(选了就没了) 完全背包:每个物品可以选无限次 区别只在代码的一个细节:内层循环的方向 0-1 背包:内层倒序(防止同一物品被选多次) 完全背包:内层正序(允许同一物品被选多次) ``` ## 大白话理解 对每个物品,只有两个选择:装进背包,或者不装。 ``` 不装物品 i:背包容量不变,价值不变 dp[j] = dp[j](保持原来的值) 装物品 i:背包容量减少 w[i],价值增加 v[i] dp[j] = dp[j - w[i]] + v[i] 取两者的最大值: dp[j] = max(dp[j], dp[j - w[i]] + v[i]) ``` ## 四步法 ``` 第 1 步:dp[j] = 背包容量为 j 时能装下的最大价值 第 2 步:dp[j] = max(dp[j], dp[j - w[i]] + v[i]) 对每个物品 i,更新所有容量 j 的 dp 值 第 3 步:dp[0..W] = 0(背包为空时价值为 0) 第 4 步:外层遍历物品,内层倒序遍历容量 为什么倒序?后面详细解释 ``` ## 二维 DP(先理解这个,再看一维优化) ``` dp[i][j] = 考虑前 i 个物品,背包容量为 j 时的最大价值 dp[i][j] = max(dp[i-1][j], 不选物品 i dp[i-1][j-w[i]] + v[i]) 选物品 i(前提:j >= w[i]) ``` ### 手动模拟(二维) ``` 物品:w=[1,3,4], v=[15,20,30], W=4 初始化(第 0 行全为 0,表示没有物品时价值为 0): j=0 j=1 j=2 j=3 j=4 i=0 [ 0 0 0 0 0 ] i=1 [ _ _ _ _ _ ] i=2 [ _ _ _ _ _ ] i=3 [ _ _ _ _ _ ] 处理物品 0(w=1, v=15): j=0: 容量 0,装不下 → dp[1][0] = dp[0][0] = 0 j=1: 容量 1 >= w=1,可以装 不装:dp[0][1] = 0 装:dp[0][1-1] + 15 = dp[0][0] + 15 = 15 dp[1][1] = max(0, 15) = 15 j=2: 容量 2 >= w=1 不装:dp[0][2] = 0 装:dp[0][2-1] + 15 = dp[0][1] + 15 = 15 dp[1][2] = 15 j=3: dp[1][3] = 15 j=4: dp[1][4] = 15 j=0 j=1 j=2 j=3 j=4 i=0 [ 0 0 0 0 0 ] i=1 [ 0 15 15 15 15 ] 处理物品 1(w=3, v=20): j=0,1,2: 容量 < w=3,装不下 → 和上一行一样 dp[2][0]=0, dp[2][1]=15, dp[2][2]=15 j=3: 容量 3 >= w=3 不装:dp[1][3] = 15 装:dp[1][3-3] + 20 = dp[1][0] + 20 = 20 dp[2][3] = max(15, 20) = 20 j=4: 容量 4 >= w=3 不装:dp[1][4] = 15 装:dp[1][4-3] + 20 = dp[1][1] + 20 = 15+20 = 35 dp[2][4] = max(15, 35) = 35 ← 物品0+物品1 j=0 j=1 j=2 j=3 j=4 i=0 [ 0 0 0 0 0 ] i=1 [ 0 15 15 15 15 ] i=2 [ 0 15 15 20 35 ] 处理物品 2(w=4, v=30): j=0,1,2,3: 容量 < w=4,装不下 → 和上一行一样 dp[3][0]=0, dp[3][1]=15, dp[3][2]=15, dp[3][3]=20 j=4: 容量 4 >= w=4 不装:dp[2][4] = 35 装:dp[2][4-4] + 30 = dp[2][0] + 30 = 30 dp[3][4] = max(35, 30) = 35 ← 不装物品2更好 j=0 j=1 j=2 j=3 j=4 i=0 [ 0 0 0 0 0 ] i=1 [ 0 15 15 15 15 ] i=2 [ 0 15 15 20 35 ] i=3 [ 0 15 15 20 35 ] 答案 = dp[3][4] = 35 ✓(选物品0+物品1) ``` ## 一维优化(滚动数组) ``` 观察二维 dp:dp[i][j] 只依赖 dp[i-1][...](上一行) 可以用一维数组滚动更新,节省空间 ``` ### 为什么内层必须倒序? ``` 正序遍历(错误): 处理物品 0(w=1, v=15)时: j=1: dp[1] = max(dp[1], dp[0]+15) = 15 j=2: dp[2] = max(dp[2], dp[1]+15) = max(0, 15+15) = 30 ← 错了! dp[1] 已经被更新为 15(包含了物品0), dp[2] 又用了更新后的 dp[1],相当于物品0被选了两次! 倒序遍历(正确): 处理物品 0(w=1, v=15)时: j=4: dp[4] = max(dp[4], dp[3]+15) = 15 (dp[3] 还是旧值 0) j=3: dp[3] = max(dp[3], dp[2]+15) = 15 (dp[2] 还是旧值 0) j=2: dp[2] = max(dp[2], dp[1]+15) = 15 (dp[1] 还是旧值 0) j=1: dp[1] = max(dp[1], dp[0]+15) = 15 (dp[0] 还是旧值 0) 每次用的都是旧值,物品0只被选了一次 ✓ ``` ### 手动模拟(一维,倒序) ``` 物品:w=[1,3,4], v=[15,20,30], W=4 dp = [0, 0, 0, 0, 0] 处理物品 0(w=1, v=15),倒序 j=4..1: j=4: dp[4] = max(dp[4], dp[4-1]+15) = max(0, dp[3]+15) = max(0, 0+15) = 15 j=3: dp[3] = max(dp[3], dp[3-1]+15) = max(0, dp[2]+15) = max(0, 0+15) = 15 j=2: dp[2] = max(dp[2], dp[2-1]+15) = max(0, dp[1]+15) = max(0, 0+15) = 15 j=1: dp[1] = max(dp[1], dp[1-1]+15) = max(0, dp[0]+15) = max(0, 0+15) = 15 dp = [0, 15, 15, 15, 15] 处理物品 1(w=3, v=20),倒序 j=4..3: j=4: dp[4] = max(dp[4], dp[4-3]+20) = max(15, dp[1]+20) = max(15, 15+20) = 35 j=3: dp[3] = max(dp[3], dp[3-3]+20) = max(15, dp[0]+20) = max(15, 0+20) = 20 dp = [0, 15, 15, 20, 35] 处理物品 2(w=4, v=30),倒序 j=4..4: j=4: dp[4] = max(dp[4], dp[4-4]+30) = max(35, dp[0]+30) = max(35, 0+30) = 35 dp = [0, 15, 15, 20, 35] 答案 = dp[4] = 35 ✓ ``` ## 代码 ```java public int knapsack(int[] w, int[] v, int W) { int[] dp = new int[W + 1]; for (int i = 0; i < w.length; i++) { for (int j = W; j >= w[i]; j--) { // 倒序! dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]); } } return dp[W]; } ``` ## 0-1 背包 vs 完全背包 代码对比 ```java // 0-1 背包(每个物品最多选 1 次) for (int i = 0; i < n; i++) { for (int j = W; j >= w[i]; j--) { // 倒序 dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]); } } // 完全背包(每个物品可以选无限次) for (int i = 0; i < n; i++) { for (int j = w[i]; j <= W; j++) { // 正序 dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]); } } // 就这一个方向的区别! ``` ## 实战:分割等和子集(LeetCode 416) ### 题目 给定一个只包含正整数的数组,判断是否可以将其分割成两个子集,使得两个子集的元素和相等。 ``` 输入:[1, 5, 11, 5] 输出:true([1, 5, 5] 和 [11]) ``` ### 转化为 0-1 背包 ``` 两个子集和相等 → 每个子集的和 = 总和 / 2 问题变成:能否从数组中选一些数,使它们的和恰好等于 sum/2? 这就是 0-1 背包: 物品 = 数组中的每个数 重量 = 数字的值 价值 = 数字的值(重量和价值相同) 背包容量 = sum/2 目标:能否恰好装满背包(dp[sum/2] == sum/2) ``` ```java public boolean canPartition(int[] nums) { int sum = Arrays.stream(nums).sum(); if (sum % 2 != 0) return false; // 总和为奇数,不可能分割 int target = sum / 2; boolean[] dp = new boolean[target + 1]; dp[0] = true; // 凑出 0 是可能的(什么都不选) for (int num : nums) { for (int j = target; j >= num; j--) { // 倒序(0-1 背包) dp[j] = dp[j] || dp[j - num]; } } return dp[target]; } ``` ### 手动模拟 [1, 5, 11, 5] ``` sum = 22, target = 11 dp = [T, F, F, F, F, F, F, F, F, F, F, F] 0 1 2 3 4 5 6 7 8 9 10 11 处理 num=1,倒序 j=11..1: j=1: dp[1] = dp[1] || dp[0] = F || T = T dp = [T, T, F, F, F, F, F, F, F, F, F, F] 处理 num=5,倒序 j=11..5: j=6: dp[6] = dp[6] || dp[1] = F || T = T j=5: dp[5] = dp[5] || dp[0] = F || T = T dp = [T, T, F, F, F, T, T, F, F, F, F, F] 处理 num=11,倒序 j=11..11: j=11: dp[11] = dp[11] || dp[0] = F || T = T dp = [T, T, F, F, F, T, T, F, F, F, F, T] 处理 num=5,倒序 j=11..5: j=11: dp[11] = dp[11] || dp[6] = T || T = T(已经是 T) j=10: dp[10] = dp[10] || dp[5] = F || T = T j=6: dp[6] = dp[6] || dp[1] = T || T = T(已经是 T) j=5: dp[5] = dp[5] || dp[0] = T || T = T(已经是 T) dp = [T, T, F, F, F, T, T, F, F, F, T, T] 答案 = dp[11] = true ✓ ``` ## 一句话总结 0-1 背包:`dp[j] = max(dp[j], dp[j-w]+v)`,内层倒序防止重复选。完全背包改正序。 --- 上一篇:[11 - 单词拆分](./11-word-break.md) | 返回:[目录](./README.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入