贪心算法，又名贪婪策略，其核心思想是在每一步决策时选择当前最优选项，以期望最终得到全局最优解。
应用领域：
哈夫曼树
最小生成树算法：Prim 和 Kruskal
最短路径算法：Dijkstra
示例1：最佳装载问题（海盗版）
在北美东南部，有一片神秘的海域，海盗在这里最为活跃。某日，海盗们抓获了一艘满载珍贵古董的船只。这些古董一旦破碎便不再具备价值，而海盗船的载重量为 W。每件古董的重量为 i，海盗们如何才能将尽可能多的古董装上海盗船呢？
例如，W 为 30，古董重量分别为 3、5、4、10、7、14、2、11。
◼ 贪心策略：每次选择最轻的古董
① 先选择重量为 2 的古董，剩余载重量 28
② 再选择重量为 3 的古董，剩余载重量 25
③ 接着选择重量为 4 的古董，剩余载重量 21
④ 然后选择重量为 5 的古董，剩余载重量 16
⑤ 最后选择重量为 7 的古董，剩余载重量 9
最多能装载 5 件古董。
代码示例：
示例2：零钱兑换
设有 25 分、10 分、5 分和 1 分的硬币，如何找给客户 41 分的零钱以使硬币数量最少？
◼ 贪心策略：每次选择面值最大的硬币
① 选择 25 分的硬币，剩余 16 分
② 然后选择 10 分的硬币，剩余 6 分
③ 接着选择 5 分的硬币，剩余 1 分
④ 最后选择 1 分的硬币
最终总共使用了 4 枚硬币：25 分、10 分、5 分和 1 分各一枚。
另一例：假设硬币面额为 25 分、20 分、5 分和 1 分，要找给客户 41 分的零钱。如何减少硬币数量？
◼ 贪心策略：每一步选择面值最大的硬币
① 先选择 25 分的硬币，剩余 16 分
② 接着选择 5 分的硬币，剩余 11 分
③ 再选择 5 分的硬币，剩余 6 分
④ 继续选择 5 分的硬币，剩余 1 分
⑤ 最后选择 1 分的硬币
最终结果是：1 枚 25 分、3 枚 5 分、1 枚 1 分，共 5 枚硬币。
◼ 实际上，最优解是：2 枚 20 分和 1 枚 1 分，共 3 枚硬币。
注意：
贪心算法并非总能保证全局最优解，因为它依赖于局部最优选择，可能会错过整体最优。它常常在没有考虑所有可能性的情况下做出决策，因此可能不如全面分析准确。
◼ 优点：算法简单高效，无需穷举所有可能，通常用于其他算法的辅助。
◼ 缺点：局限于局部最优解，可能无法回溯和调整，通常不提供最优解。
示例3：0-1背包问题
给定 n 件物品和一个最大承重为 W 的背包，每件物品的重量和价值相同，如何在保证背包总重量不超过 W 的情况下，使背包的总价值最大化？
◼ 注意：每件物品只能选择 0 件或 1 件，因此称为 0-1 背包问题。
◼ 贪心策略有三种方案：
① 价值优先：优先选择价值最高的物品
② 重量优先：优先选择重量最轻的物品
③ 价值密度优先：优先选择价值密度最高的物品（价值密度 = 价值 ÷ 重量）
代码实现：
1）定义一个类：
2）实现算法：
3) 测试结果：