0/1 背包：取或不取
在重量上限内最大化价值
0/1 背包：取或不取 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
背包问题的故事
您有一个有重量限制的背包和一堆物品。0/1 背包要解决的问题是：在不超出容量的前提下，选择哪些物品才能使价值最大？🎒
选择或放弃
0/1表示每件物品要么完整取走，要么完全跳过。您不能拿走半件物品，因此每次选择都只有取或不取两种可能。
为什么贪心法会失败
先拿最轻或价值最高的物品，可能会浪费容量。贪心捷径在这里并不成立，因此需要考虑真正的物品组合。
两个输入
给定两个一一对应的列表：每件物品的重量和值，以及一个容量。第 i 件物品的重量为 wt[i]，价值为 val[i]。
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7定义状态
令 dp[i][w] 表示在容量为 w 时使用前 i 件物品所能获得的最大价值。准确地命名状态是解决问题的关键。
跳过选择
如果跳过第 i 件物品，价值就是已有的价值：dp[i-1][w]。剩余物品仍然可以使用全部容量。
拿取选择
如果拿取第 i 件物品，就加上它的价值并减少容量：val[i] + dp[i-1][w - wt[i]]。只有当 w 至少为 wt[i] 时，这个选择才合法。
选择更优的分支
递推式只需用 max 保留两个选项中较大的那个。每个单元格都依赖于已经计算好的子问题答案。
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])基础行
没有物品时，无论容量是多少，都只能获得 0 的价值。这个边界条件将第一行全部填为 0，为后续计算提供基础。
dp = [[0] * (cap + 1) for _ in range(n + 1)]填充表格
外层遍历物品，内层遍历容量。每个单元格只读取上方的那一行，因此一次遍历就能填满整张表。
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]读取答案
右下角的单元格 dp[n][cap] 保存了使用所有物品且容量为 cap 时的最大价值。这个单元格就是最终答案。
快速检查
测试 0/1 背包的核心递推式。
回顾
您已经学会了 0/1 背包：每件物品都只能选择取或不取，dp[i][w] 会在跳过和拿取之间保留更优值，而 dp[n][cap] 就是答案。🎉
用 AI 导师学习 Python — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 30
- 课程
- 120
常见问题解答
「0/1 背包：取或不取」课时是免费的吗？
是的 — 「0/1 背包：取或不取」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「0/1 背包：取或不取」这节课中我会学到什么？
在重量上限内最大化价值 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「0/1 背包：取或不取」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 0/1 背包：取或不取
- 空间优化的背包
- 完全背包与换零钱 DP
- 子集和与划分