《算法的乐趣》第十节

贪婪法的设计分三步：建立最优解的数学模型、把问题分解为一系列子问题并定义其最优解结构、用贪心原则逐个求子问题的局部最优解再堆叠成全局解。

贪婪法的设计分三步：建立最优解的数学模型、把问题分解为一系列子问题并定义其最优解结构、用贪心原则逐个求子问题的局部最优解再堆叠成全局解。子问题可按求解过程逐步推进，也可拆成相对独立的几块再组合。以找零41分为例，币值为25、10、5、1分时，每次取不超过总额的最大币值，四枚硬币即为最优；但若币值改为25、20、5、1分，贪婪法给出5枚，而两枚20分加一枚1分只需3枚，说明贪婪法未必得到最优解。

0-1背包问题是贪婪法的经典例子：N件不可分割的物品、承重C的背包，求总重不超C且总价值最大的选取方案。以C=150、7件物品为例，子问题按逐步装包分解，每选一件容量就减小。三种策略结果不同：按价值选（编号4、2、6、5）总重130、价值165；按重量选（6、7、2、1、5）总重140、价值155；按价值密度pi/wi选（6、2、7、4、1）总重150、价值170，与动态规划的最优解一致，但换组数据结论可能相反。实现上，物品结构含重量、价值和选择状态（状态2表示该物品导致超重，今后不再选），GreedyAlgo()函数通过替换选择策略函数接口实现不同策略。贪婪法在能证明最优的问题（如Prim、Kruskal求最小生成树）中高效，多数情况只能得到近似解，但作为启发式方法常用于Dijkstra等算法中；任何阶段只考虑局部最优的选择都可视为贪婪算法。

分治法把大问题分解成规模更小、形式相同的子问题逐个求解，反复分解直到可直接求解，目的是让难题变易并降低计算量。应用分三步：分解为相互独立且子结构相同的子问题；可解则解之，否则递归再分解；按规则合并各子解得到原解。快速排序以标兵数分组再拼接，快速傅里叶变换按奇偶拆成两个N/2点变换再按蝶形运算重排，Karatsuba乘法把n位大数拆成a+b，用公式化为三次乘法和移位再求和。难点在于分解与合并方式，能用数学归纳法证明的问题通常可用分治法解决。