每一步都先选眼前看起来最好的那个——有时候这样真的能拿到全局最优解，但不是每次都行。
贪心算法的策略很直接：每走一步，都选当前看起来最好的那个选择，走完之后不再回头修改——不去比较"如果当时选了别的会怎样"，只管眼前这一步怎么选最划算。
这和 2.1 节的枚举法刚好相反：枚举法是"所有可能都试一遍，比较着找最优"，贪心算法是"想都不用想，每一步直接选最优的那个"——快很多，但不是每一道题都能这样做。关键在于：选了眼前最好的，最后凑出来的整体方案，是不是也一定是最好的？这一节用两个经典例子，一个"贪心能成功"，一个"贪心会失败"，把这件事讲清楚。
有 6 个活动，每个活动有固定的起止时间，同一时间只能参加一个活动（时间不能有重叠），问最多能参加多少个活动？活动列表：(1,3) (2,5) (4,7) (6,9) (8,10) (9,11)。
贪心策略：每次都选"结束时间最早"的那个活动（前提是它和已经选中的活动不冲突）。直觉上，结束得越早，留给后面的时间就越多，越不容易挡住后续的选择。
(1,3)；下一个能选的、且和 (1,3) 不冲突（开始时间 ≥ 3）里结束最早的是 (4,7)，跳过了 (2,5)（虽然它也不冲突，但结束更晚，会挡住更多后续机会）；接着同理选中 (8,10)，跳过 (6,9)。最终选中 3 个活动：(1,3) (4,7) (8,10)——经过暴力穷举验证，3 确实是这道题能选到的最多活动数，贪心策略给出了正确答案。| 1 | struct Activity |
| 2 | { |
| 3 | int start, end; |
| 4 | }; |
| 5 | |
| 6 | int MaxActivities(vector<Activity> activities) |
| 7 | { |
| 8 | sort(activities.begin(), activities.end(), [](Activity a, Activity b) { |
| 9 | return a.end < b.end; // 按结束时间从小到大排序 |
| 10 | }); |
| 11 | |
| 12 | int count = 0; |
| 13 | int lastEnd = -1; // 上一个选中活动的结束时间 |
| 14 | for (Activity a : activities) |
| 15 | { |
| 16 | if (a.start >= lastEnd) // 和上一个选中的活动不冲突 |
| 17 | { |
| 18 | count++; |
| 19 | lastEnd = a.end; |
| 20 | } |
| 21 | } |
| 22 | return count; |
| 23 | } |
有 3 种物品，背包能装的总重量是 50。每种物品都可以只取一部分（比如取半袋大米，重量和价值都按比例打对折）——这一点很重要，因为它决定了贪心策略能不能用，下一节会说明为什么。三种物品：
| 物品 | 重量 | 价值 | 性价比（价值÷重量） |
|---|---|---|---|
| A | 10 | 60 | 6.0 |
| B | 20 | 100 | 5.0 |
| C | 30 | 120 | 4.0 |
贪心策略：按"性价比"从高到低排序，能装多少就先装多少——先把性价比最高的物品尽量整个装满，背包还有剩余空间再装下一个性价比高的，直到背包装满为止。
40；再整个装入 B（重20、值100），剩余容量 20；最后剩余容量不够装下整个 C（重30），只装入 20/30 = 2/3，对应价值 120 × 2/3 = 80。三部分加起来总价值 60 + 100 + 80 = 240，这正是部分背包问题的最优解。| 1 | struct Item |
| 2 | { |
| 3 | double weight, value; |
| 4 | }; |
| 5 | |
| 6 | double FractionalKnapsack(vector<Item> items, double capacity) |
| 7 | { |
| 8 | sort(items.begin(), items.end(), [](Item a, Item b) { |
| 9 | return a.value / a.weight > b.value / b.weight; // 性价比从高到低 |
| 10 | }); |
| 11 | |
| 12 | double totalValue = 0; |
| 13 | for (Item it : items) |
| 14 | { |
| 15 | if (capacity >= it.weight) // 装得下整个物品 |
| 16 | { |
| 17 | totalValue += it.value; |
| 18 | capacity -= it.weight; |
| 19 | } |
| 20 | else // 装不下整个，只装能装下的那一部分 |
| 21 | { |
| 22 | totalValue += it.value * (capacity / it.weight); |
| 23 | break; // 背包已经装满，结束 |
| 24 | } |
| 25 | } |
| 26 | return totalValue; |
| 27 | } |
两个例子都成功了，但千万不要因此觉得贪心总是管用。换一个看起来很像的问题——把"部分背包"改成"0/1 背包"：每种物品要么整个拿走，要么完全不拿，不能只拿一部分。这个小小的改动，会让"按性价比贪心"彻底失效。
10，值 60，性价比 6）、物品 B（重 20，值 100，性价比 5），背包容量 20，这次不允许只拿一部分。按性价比贪心，先拿 A（重10，值60），剩余容量 10，装不下整个 B 了——贪心只能拿到 60。但实际上，只拿 B 一个（重20，正好装满，值100）反而更好——100 > 60。贪心策略在这里给出了错误答案。| 问题 | 贪心策略 | 贪心是否有效 |
|---|---|---|
| 区间调度 | 按结束时间从早到晚选择 | ✓ 有效，能得到最优解 |
| 部分背包 | 按性价比从高到低尽量多装 | ✓ 有效，能得到最优解 |
| 0/1 背包 | 按性价比从高到低尽量多装 | ✗ 无效，可能得到错误答案 |