小学四年级也能掌握的贪心算法（2、第 2 课：先排队，再做决定！）

贪心算法

第 2 课：先排队，再做决定！

上一课，我们认识了贪心算法，知道了一个重要的想法：

每一步都优先选择当前看来最好的方案。

可是，乐乐很快遇到了一个新问题。

如果面前有 100 件商品、100 个任务，难道每次都要一件一件地找吗？

有没有一种办法，能让这些东西先排好队，让我们更容易作出选择？

当然有！今天，我们就要学习一个非常重要的搭档：

排序 + 贪心。

一、第一关：魔法商店大采购

乐乐来到了一家魔法商店。商店正在举行特价活动，每件商品只能买一件。

乐乐的口袋里有 10 枚金币，他想买尽可能多的商品。

商店里有以下 4 件商品：

规则很简单：

• 每件商品只能买一次。

• 不能超出 10 枚金币的预算。

• 我们的目标是：买到尽可能多的商品。

请先想一想：应该先买哪件商品？

A、先买 6 金币的魔法棒

B、先买 2 金币的魔法药水

C、先买 5 金币的水晶球

D、先买 3 金币的魔法糖果

再看看题目目标：不是买最贵的商品，也不是买最喜欢的商品，而是要买到尽可能多的商品。哪件商品最便宜呢？

这里，我们发现了一件事：

选择规则不是随便规定的，而是由题目目标决定的。

目标是买最多件商品，所以我们可以尝试先买便宜的商品。

但商品越来越多时，怎样快速找到便宜的商品呢？这就需要排序了！

二、第二关：让商品排好队

想象一下，4 件商品正在魔法商店里乱糟糟地站着：

排好队以后，我们就不需要到处寻找最便宜的商品了。

第一件最便宜，第二件次便宜，第三件更贵……

我们只需要从队伍的最前面开始，依次检查就可以了！

1. C++ 中怎样排序？

在 C++ 中，我们可以使用 sort() 函数。

先看一个最简单的例子：

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
int price[4] = {6, 2, 5, 3};

sort(price, price + 4);

for (int i = 0; i < 4; i++)
{
cout << price[i] << " ";
}

return 0;
}

运行结果：

2 3 5 6

我们来认识其中几个关键部分。

代码

小学生版解释

这里最重要的是：

sort(price, price + 4);

你可以把它想象成一位排队管理员，把乱序的数字重新整理好。

注意：sort() 默认是从小到大排序。这里的 price + 4 表示排序范围的结束位置，但不包含这个位置。

三、第三关：按顺序购买，看看能买多少件

现在，我们把排序和贪心结合起来。

乐乐有 10 枚金币，商品价格是：

6、2、5、3

我们先排序，再依次购买。

第一步：从小到大排序

得到：

2、3、5、6

第二步：从最便宜的开始买

我们发现，只要按照价格从低到高的顺序购买，就能在预算允许的情况下尽可能多买商品。

为什么？

因为每件商品都只能买一件，而且我们的目标是买的件数最多。购买更便宜的商品，会给后续选择留下更多预算；换成更贵的商品，并不会让购买件数增加。

这就是一道非常典型的“排序 + 贪心”问题。

四、第四关：把购买过程写成程序

接下来，我们要把刚才的手工操作翻译成 C++。

先记住一个简单规则：

• 如果当前商品买得起，就购买。

• 如果买得起，就扣除价格，并让商品数量加 1。

• 如果买不起，就不购买。

为了方便初学者理解，我们采用“买不起就跳过”的写法。因为价格已经从小到大排序了，如果当前商品买不起，后面更贵的商品也买不起，所以可以直接结束循环。

完整程序如下：

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
int n = 4;
int money = 10;
int price[100] = {6, 2, 5, 3};

// 第一步：按价格从小到大排序
sort(price, price + n);

// 第二步：统计买到的商品数量
int cnt = 0;

// 第三步：从便宜的商品开始检查
for (int i = 0; i < n; i++)
{
if (price[i] <= money)
{
money = money – price[i];
cnt++;
}
else
{
break;
}
}

cout << "最多可以买 " << cnt << " 件商品" << endl;
cout << "剩余金币：" << money << endl;

return 0;
}

运行结果：

最多可以买 3 件商品
剩余金币：0

代码逐行拆解

代码

作用

这里有两个变量一定要分清楚：

• money：还剩多少金币。

• cnt：已经买到了多少件商品。

一个记录钱，一个记录数量，它们的任务不同。

五、第五关：换一种排序规则，会发生什么？

乐乐发现，排序很方便，于是他问智慧猫头鹰：

“既然排序这么厉害，是不是把所有东西排个队，再从前往后选，就一定能得到最好的答案？”

智慧猫头鹰回答：

“还不够！排序的依据必须和题目的目标有关。”

我们做一个小实验。

还是那 4 件商品，价格分别是 6、2、5、3，预算是 10 枚金币。

如果我们按照价格从大到小排序：

6、5、3、2

先买 6 枚金币的商品，剩余 4 枚；接着 5 枚金币的商品买不起，后面的商品更便宜，但我们如果直接结束，就只买到 1 件商品。

可是，这样做真的对吗？

当然不对！因为我们已经知道，这道题按价格从小到大购买，可以买到 3 件。

所以，不是只要排序就可以，而是要先确定合适的排序规则。

对于今天的采购问题：

• 目标：买到尽可能多的商品。

• 规则：优先买价格低的商品。

• 实现：价格从小到大排序。

• 执行：依次购买，直到剩余金币不足。

这四步合在一起，才是完整的解题思路。

六、第六关：课堂闯关练习

我们来检查一下，今天学会了多少。

挑战 1：排队小能手

数字 7、2、9、4 使用 sort() 从小到大排序，结果是什么？

A、2、4、7、9

B、9、7、4、2

C、2、7、4、9

答案：A

从小到大排列，得到 2、4、7、9。

挑战 2：金币采购员

你有 8 枚金币，商品价格分别是 5、2、3、4，每件商品只能买一次。为了买到尽可能多的商品，应该优先按什么顺序选择？

A、价格从大到小

B、价格从小到大

C、按照原来的顺序，不用考虑价格

答案：B

目标是购买最多件商品，因此优先购买便宜的商品。

挑战 3：剩余金币

商品价格已经从小到大排好队。当前剩余 3 枚金币，下一个商品价格是 5 枚金币。后面商品的价格只会更高，应该怎么做？

A、继续购买

B、结束循环，因为后面更贵的商品也买不起

C、把金币变成 5 枚

答案：B

价格已从小到大排列，后面只会更贵，可以结束循环。

七、课后小任务：给乐乐写一份采购程序

请你试着修改课堂上的程序，完成下面这个小任务。

乐乐有 12 枚金币，商店里有 5 件商品，价格分别是：

7、2、6、3、4

要求：

提示：你只需要修改商品数量、预算和价格数组，其他代码可以先保持不变。

八、本课总结：贪心算法的第一个常用模板

记住这四个步骤

1、确定目标

例如：买到尽可能多的商品。

2、确定排序规则

例如：价格从小到大排序。

3、依次作出选择

买得起就购买，同时更新金币和商品数量。

4、得到最终答案

输出买到的商品数量和剩余金币。

今天我们第一次把贪心思想与 C++ 中的 sort()、for、if 和 break 结合起来，解决了一个完整的问题。

请记住一句话：

先想清楚为什么这样排，再决定怎样选。

排序是工具，贪心策略才是解题的关键。

下一课，我们将进入第 3 课：零钱魔法师——硬币与资源选择，探索如何用不同面值的硬币凑出目标金额，以及为什么有些硬币问题能使用贪心，有些却不能。