每一步都先选眼前最好的——有时候这样能得到最好的结果，有时候不行。
贪心算法的想法特别简单：每一步都选眼前最好的那个，选完就不再反悔。
举个例子：你付了 100 元，收银员要找你 41 元，怎么找，钞票的张数最少？聪明的办法是——每次都先拿“不超过剩下数目的最大面额”：先拿 20 元，再拿 20 元，最后拿 1 元，一共只要 3 张。这就是贪心：每一步都挑最大的，不用把所有找钱的办法都试一遍。
这和 2.1 节的枚举法正好相反：枚举法是“把所有办法都试一遍，再挑最好的”，贪心是“每一步直接选最好的”，所以快得多。但有个大问题：每一步都选最好的，合起来一定是最好的吗？有时候是，有时候不是。这一节用三个例子来讲清楚：前两个，贪心能成功；第三个，贪心会失败。
学校社团有 6 个活动，每个活动都有开始和结束的时间。你同一时间只能参加一个活动，最多能参加几个？6 个活动是：(1,3) (2,5) (4,7) (6,9) (8,10) (9,11)。比如 (1,3) 表示 1 点开始、3 点结束。
先说清楚什么叫冲突：两个活动的时间重叠了，就是冲突。比如 (1,3) 和 (2,5)：2 点就开始了，可是 (1,3) 要到 3 点才结束，所以不能两个都参加。而 (1,3) 和 (4,7) 不冲突，因为 3 点结束以后，4 点才开始。（刚好 3 点结束、3 点开始，也算不冲突。）
贪心的办法：每次都选“结束得最早”的活动（前提是和已经选好的不冲突）。想一想：活动结束得越早，后面剩下的时间就越多，能参加的活动也就越多。
(1,3)。(2,5)：2 点就开始了，但 (1,3) 3 点才结束，重叠了，不能选。(4,7)：4 点开始，在 (1,3) 结束之后，可以选。(6,9)：6 点开始，但 (4,7) 7 点才结束，重叠了，不能选。(8,10)：8 点开始，在 7 点之后，可以选。(9,11)：9 点开始，但 (8,10) 10 点才结束，重叠了，不能选。(1,3) (4,7) (8,10)，3 个就是最多的了。| 1 | struct Act // 一个活动 |
| 2 | { |
| 3 | int s, e; // 开始时间、结束时间 |
| 4 | }; |
| 5 | |
| 6 | int MaxAct(vector<Act>& a) |
| 7 | { |
| 8 | sort(a.begin(), a.end(), [](const Act& x, const Act& y) { |
| 9 | return x.e < y.e; // 结束得早的排在前面 |
| 10 | }); |
| 11 | |
| 12 | int cnt = 0; // 已经选了几个 |
| 13 | int last = 0; // 上一个选中活动的结束时间 |
| 14 | for (const Act& it : a) |
| 15 | { |
| 16 | if (it.s >= last) // 开始得不比上一个的结束时间早，不冲突 |
| 17 | { |
| 18 | cnt++; |
| 19 | last = it.e; |
| 20 | } |
| 21 | } |
| 22 | return cnt; |
| 23 | } |
代码分两步：第一步，先把活动按结束时间从早到晚排好队；第二步，从前往后看，如果这个活动的开始时间不比上一个选中活动的结束时间早，就选它，并记下它的结束时间。
(1,3) 比 (2,5) 结束得更早，所以排在后面的 (6,9)、(9,11) 一定不会和它撞上。换完以后活动一个都没少。(2,5)，不是结束最早的。(2,5) 换成 (1,3)。(1,3) 结束得比 (2,5) 还早，后面的活动本来就排在后面，当然不会和它撞上。(1,3) 的安排，不会比任何人的安排差。(1,3) 以后，剩下的活动又是一道一模一样的题，再用同样的办法选，每一步都不会吃亏。有一个背包，最多能装 50 千克。有 3 种东西，每种都可以只拿一部分（比如半袋大米，重量和价值都变成一半）。怎样装，背包里东西的总价值最大？“可以只拿一部分”这一点非常重要，后面会讲为什么。
| 物品 | 重量（千克） | 价值（元） | 性价比（每千克值多少钱） |
|---|---|---|---|
| A | 10 | 60 | 6.0 |
| B | 20 | 100 | 5.0 |
| C | 30 | 120 | 4.0 |
“每千克值多少钱”叫性价比，用价值 ÷ 重量算出来。A 每千克值 6 元，最划算；C 每千克只值 4 元，最不划算。
贪心的办法：先装性价比最高（最划算）的，能整个装就整个装；装不下了，就切一部分，把背包正好装满。
40 千克的空位。20 千克的空位。20 千克，也就是 C 的 2/3，价值 120 × 2/3 = 80 元。60 + 100 + 80 = 240 元，这就是最大的。| 1 | struct Item // 一件物品 |
| 2 | { |
| 3 | int w, v; // 重量、价值 |
| 4 | }; |
| 5 | |
| 6 | double Knap(vector<Item>& a, int cap) // cap：背包还能装多少 |
| 7 | { |
| 8 | sort(a.begin(), a.end(), [](const Item& x, const Item& y) { |
| 9 | return x.v * y.w > y.v * x.w; // 每千克更值钱的排在前面 |
| 10 | }); |
| 11 | |
| 12 | double sum = 0; // 装进背包的总价值 |
| 13 | for (const Item& it : a) |
| 14 | { |
| 15 | if (cap >= it.w) // 装得下整件 |
| 16 | { |
| 17 | sum += it.v; |
| 18 | cap -= it.w; |
| 19 | } |
| 20 | else // 装不下整件，只装一部分 |
| 21 | { |
| 22 | sum += (double)it.v * cap / it.w; |
| 23 | break; // 背包装满了，结束 |
| 24 | } |
| 25 | } |
| 26 | return sum; |
| 27 | } |
代码的步骤和上面一样：先按性价比从高到低排好队，再一件一件装；装得下整件就整件装，装不下就装一部分，然后结束。
4 元），而最划算的 A（每千克值 6 元）还没装满。把 1 千克 C 拿出来，换成 1 千克 A：背包的重量没变，价值反而多了 6 − 4 = 2 元。东西能切，就能这样一点一点地换，而且每换一次都只赚不亏。一直换到 A 装满为止，再用同样的办法处理 B——所以先把最划算的装满，一定不会比别的装法差。int（整数）存，不用小数，这样不会有误差。x.v * y.w > y.v * x.w（交叉相乘），而不是 x.v / x.w > y.v / y.w。因为除法算出来的小数，最后一位可能有一点点误差；乘法全是整数，不会出错。(double)it.v * cap / it.w：一定要先把数变成 double（小数）再算，不然整数相除会把小数部分直接丢掉（比如 100 * 20 / 30 会算成 66，而不是 66.67）。vector 前面写的 & 表示“直接用原来的数组，不复制一份”，会更快；不过这样 sort 会把原数组的顺序改掉。两个例子都成功了，但千万不要觉得贪心总是管用。我们把“部分背包”改一改，变成“0/1 背包”：每件东西要么整件拿走，要么不拿，不能只拿一部分（就像一台电脑，不能锯一半带走）。就这么一点改动，“先装最划算的”就可能出错了。
10，值 60）、B（重 20，值 100）、C（重 30，值 120），背包还是最多装 50 千克，但这次每件只能整件拿，或者不拿。40 千克），再拿 B（还剩 20 千克），C 重 30，装不下了。总价值 60 + 100 = 160 元，背包里还白白空着 20 千克。20 + 30 = 50，正好装满，总价值 100 + 120 = 220 元，比贪心多了 60 元。240，0/1 背包用贪心只有 160，真正最好的是 220。20 千克，还能装上 C 的 2/3（值 80 元），一点空位都不浪费。0/1 背包不能切，这 20 千克只能空着。“性价比最高”只有在“能把背包装满”的时候，才等于“总价值最高”；装不满，浪费掉的空位就是白白损失的价值。所以 0/1 背包要用动态规划来做（见 13.2 背包问题）：它会把“拿”和“不拿”两种选择都比较一遍。贪心选了就不回头，动态规划会把所有可能都考虑到。| 对比 | 部分背包 | 0/1 背包 |
|---|---|---|
| 东西能不能切开 | 能（大米、金沙） | 不能（电脑、手机） |
| 背包能不能装满 | 总能装满，切一块塞进空位 | 可能留下一块什么也放不进的空位 |
| 先装最划算的 | ✓ 一定是最好的 | ✗ 可能出错 |
| 正确的做法 | 贪心 | 动态规划 |
| 问题 | 贪心的办法 | 贪心对不对 |
|---|---|---|
| 区间调度 | 先选结束最早的 | ✓ 对，能得到最多的活动 |
| 部分背包 | 先装性价比最高的 | ✓ 对，能得到最大的价值 |
| 0/1 背包 | 先装性价比最高的 | ✗ 不一定，可能得到错误答案 |