Hello-Algo Greedy Chapter Exercises: Guided Solutions and Source-Level Walkthroughs【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo《Hello 算法》Greedy贪心章节的配套练习文档覆盖三个经典场景零钱兑换、分数背包、最大容量问题其中分数背包还给出了需要自行完成的编程练习题。本文以 exercises.md 为骨架逐题给出推导过程、标准答案并结合仓库内可运行的源码Python 实现展示贪心策略的落地方式帮助读者把贪心选择性质从直觉理解提升到可验证的代码层面。练习结构总览这套题在考察什么本章练习分为两大部分与章节正文逐一对应练习对应正文章节考察要点概念回顾 · 选最大面额硬币greedy_algorithm.md贪心策略的局限性与贪心选择性质的证伪方式概念回顾 · 背包先装哪个物品fractional_knapsack_problem.md单位价值value per unit weight的正确比较方式概念回顾 · 移动哪根指针max_capacity_problem.md双指针贪心的安全性论证为什么只能移动短板编程练习 · 分数背包同上将贪心思路写成可运行代码并返回最大总价值前三个问题主要训练识别贪心策略 构造反例/证明其正确性的思维最后一个问题则要求把算法翻译成程序。读者可先独立作答再对照下面的推导核对。概念回顾一永远选择最大面额硬币是正确策略吗题目与标准答案给定硬币面额[1, 7, 10]目标金额为 14采用规则每次都选择不超过剩余金额的最大面额硬币按规则写出被选中的硬币序列是否存在用更少硬币凑出 14 的方案若存在请给出否则说明原因该例是否能证明贪心策略对任意面额集合都正确解答要点贪心规则会得到10 1 1 1 1共5 枚。存在更优解7 7仅需2 枚。不能证明贪心正确。这个反例恰好说明当面额组合是任意值时每次取当前最大的可用面额并不能保证硬币总数最少——眼前的最大选择可能阻断后续更优的组合。与仓库源码互证这一看似正确却会翻车的性质在章节正文与可运行示例中都有体现。coin_change_greedy.py 实现了贪心版零钱兑换其while amt 0循环第 14-21 行每轮都先找到小于且最接近剩余金额的硬币再扣减。脚本的驱动代码部分第 27-48 行刻意对比了三组用例coins [1, 5, 10, 20, 50, 100]amt 186贪心可取得最优解coins [1, 20, 50]amt 60贪心得到50 1×1011 枚而最优解是20 20 203 枚coins [1, 49, 50]amt 98贪心得到50 1×4849 枚而最优解是49 492 枚。注意上述示例中的[1, 20, 50]、[1, 49, 50]是比练习中[1, 7, 10]更极端的反例用于说明贪心策略不仅可能次优还可能产生非常差的结果。正如 greedy_algorithm.md 指出的判定什么样的面额集合能被贪心算法最优求解本身就是难题正文引用了一篇给出 $O(n^3)$ 判定算法的论文Pearson, 2005。引申贪心的适用范围由这一题可以引出贪心算法的使用边界。判断问题是否适合贪心需要考察两条性质贪心选择性质局部最优选择总能导向全局最优解最优子结构原问题的最优解包含子问题的最优解。证明贪心选择性质通常并不容易而证伪相对简单——本练习正是典型的用一个反例完成证伪。与之相对零钱兑换这类问题更适合交给动态规划求解这也是正文将其与完全背包章节关联的原因。概念回顾二背包应该先放哪件物品题目与标准答案背包容量为 4 kg物品可分装价值与所取重量成正比物品 A重量 4 kg价值 20物品 B重量 3 kg价值 18。计算两件物品的每千克价值判断应优先放入哪件按分数背包的贪心策略装满背包计算最终总价值当物品可分割且背包限制总重量时应比较总价值还是单位价值为什么解答要点A 的单位价值为20 ÷ 4 5B 的单位价值为18 ÷ 3 6因此单位价值更高的B 应优先放入。贪心填充过程先整体装入 B占用 3 kg、获得价值 18剩余 1 kg 容量装 1 kg 的 A获得价值 5。最终总价值为18 5 23。当物品可分割、约束是总重量时比较基准必须是单位重量价值。尽管 A 的总价值更高但其每千克价值低于 B若先装满 A 只能得到价值 20小于 23。与仓库源码互证分数背包正文给出的贪心策略是按单位价值从高到低排序逐轮贪心取当前单位价值最高的物品若剩余容量不足以装下整件物品则取一部分填满背包。fractional_knapsack_problem.md 用反证法证明了该策略的正确性若最优解不含单位价值最高的物品 $x$则从背包中任意移除一单位重量再替换为 $x$ 的一单位重量总价值必然上升与最优矛盾。对应实现可见 fractional_knapsack.py第 16-34 行 为核心函数fractional_knapsack先按item.v / item.w单位价值降序排序再在循环中能整装则整装、不能整装则按比例(item.v / item.w) * cap装入并提前终止驱动代码第 37-46 行给出了一组可直接运行验证的示例数据wgt [10, 20, 30, 40, 50]、val [50, 120, 150, 210, 240]、cap 50。复杂度方面除排序外最坏情况需遍历全部 $n$ 件物品因此时间开销主要由排序决定内建排序通常为 $O(n \log n)$排序之外的遍历部分为 $O(n)$由于要初始化存放物品的列表空间复杂度为 $O(n)$。正文还提供了一种几何直觉把物品重量 × 单位价值看作二维坐标下的矩形分数背包问题等价于在横轴有界区间内求最大包围面积。概念回顾三下一步该移动哪根指针题目与标准答案容器隔板高度数组为[1, 8, 6, 2, 5]双指针分别位于数组两端容量 较短隔板高度 × 两隔板索引之差初始状态左指针在索引 0、右指针在索引 4当前容量是多少下一步应移动哪根指针执行第 1 问的选择后两指针位于哪些索引容量变为多少下一步应移动哪根指针对当前隔板对既可以移动较短侧指针也可以移动较高侧指针哪种移动仍可能产生更大容量为什么解答要点当前容量为min(1, 5) × (4 - 0) 4。左侧隔板更矮因此移动左指针。左指针右移一位后两指针位于索引 1 与索引 4容量为min(8, 5) × (4 - 1) 15。右侧隔板更矮下一步移动右指针。只有移动较短一侧的指针才可能使容量继续增大。因为若移动较高侧的指针宽度必然减小而高度仍受未移动的较短隔板限制容量只可能不变或减小只有移动较短隔板才可能遇到更高的隔板从而提升容量下限。与仓库源码互证该题对应的贪心策略在 max_capacity_problem.md 中表述为将两指针初始化在数组两端每轮先计算当前容量并更新最大值再比较两侧高度并向内移动较矮一侧的指针直到两指针相遇。源码实现见 max_capacity.py 的max_capacity函数第 8-24 行循环条件为while i j每轮用min(ht[i], ht[j]) * (j - i)计算容量并以res max(res, cap)更新随后通过if ht[i] ht[j]: i 1 else: j - 1移动较矮一侧。正文还解释了贪心为何安全设当前状态为 $cap[i, j]$ 且 $ht[i] ht[j]$移动矮板 $i$ 会跳过状态序列 $cap[i, i1], \dots, cap[i, j-1]$——这些恰恰等价于把高板 $j$ 向内移动所到达的状态而移动高板必然使容量不增。因此被跳过的状态不可能是最优解贪心不会漏掉答案。算法至多执行 $n$ 轮时间复杂度和空间复杂度分别为 $O(n)$ 与 $O(1)$相比穷举枚举的 $O(n^2)$ 状态数有明显提升。编程练习实现分数背包的贪心解法这是练习题中唯一需要动手写代码的部分原文档给出了三条提示逐条对应解题的三个阶段先计算每件物品的单位价值val[i] / wgt[i]并保留除法的小数部分优先把单位价值更高的物品装入背包若剩余容量小于当前物品重量则只取恰好填满背包的那一部分并停止。依据这三条提示一个可直接参考的完整实现仓库中已存在可对照阅读如下方核心逻辑class Item: def __init__(self, w: int, v: int): self.w w # 物品重量 self.v v # 物品价值 def fractional_knapsack(wgt: list[int], val: list[int], cap: int) - int: 分数背包贪心 items [Item(w, v) for w, v in zip(wgt, val)] # 按单位价值 val / wgt 从高到低排序 items.sort(keylambda item: item.v / item.w, reverseTrue) res 0 for item in items: if item.w cap: # 剩余容量充足整件装入 res item.v cap - item.w else: # 剩余容量不足按比例装入后终止 res (item.v / item.w) * cap break return res上述代码即仓库文件 fractional_knapsack.py 的实现。若读者独立作答时想验证自己的解法可先尝试上述三步提示所对应的实现再与仓库参考实现比对注意该问题的返回值是实数允许出现小数结果这正是按比例切分物品与 0-1 背包的关键差异。阅读各语言实现如 en/codes/python/chapter_greedy、en/codes/java/chapter_greedy、en/codes/cpp/chapter_greedy等目录可以进一步比较Item封装与排序在语法层面的差异。验证与自检建议完成本章练习后建议回到 summary.md 做一次知识收口用以下条目自检贪心算法是每阶段做局部最优决策以期望得到全局最优解的优化问题求解方法它适合具备贪心选择性质与最优子结构两类性质的问题其中贪心选择性质代表策略的有效性证明贪心选择性质通常比证伪更难零钱兑换是容易给出反例、难以证明成立的典型分数背包允许物品分割因此可按单位价值贪心其正确性可用反证法证明最大容量问题通过每轮移动较矮一侧指针将 $O(n^2)$ 的穷举优化到 $O(n)$安全性的关键在于被跳过的状态必非最优。如果想要动手验证实现行为可以在本仓库对应语言目录中直接运行算法文件观察输出例如用python en/codes/python/chapter_greedy/fractional_knapsack.py查看分数背包示例的运行结果再把练习中的[1, 7, 10] / 14、[1, 8, 6, 2, 5]等小型用例代入对照即可完成读题 → 手推 → 运行验证的完整闭环。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考