贪心策略

76智慧教学 2023年8

月智汇好题目

古埃及人喜欢把分数转化成分子为1的分数来进行计算，后人常把分子是1的分数称为“埃及分数”。埃及分数问题，即把一个真分数表示为最少的埃及分数之和的形式，如把59表示为12＋118。求解这类问题，常用所谓“贪心算法”。贪心算法，看到它的名字，你也许会好奇：什么样的算法会被称为贪心算法？贪心算法，又称贪婪算法，即总在每一步骤做最优决策，希望通过一系列的局部最优决策，获得问题的全局最优解。贪心算法并不从整体最优考虑，它所作出的选择只是局部最优选择。运用这种算法求解最优化问题时，每一个阶段总是做一个使局部最优的贪心选择，不断将问题转化为规模更小的子问题。下面就让我们通过一组问题，体会贪心算法在埃及分数问题里的应用吧！【题目】第1题 古埃及人如何分饼“把3块饼平均分给4个人，每人分得34块”是苏教版小学数学五年级下册《分数的意义和性质》单元的学习内容，常见的分法有两种：一种是每次分1块饼，每人分得3个14块；另一种是3块一起分，每人分得3块的14。其实，4000多年前的古埃及人也会遇到分饼的问题，你能根据图1，说说古埃及人是怎么将3块饼平均分给4个人的吗？1212121214141414图1第2题 贪心法古埃及人在均分物品时，总会先保证每人分到1份且每次只取其中的1份，在此前提下用最少的次数分完物品，每次争取分到的最多，有人把这种分法称为贪心法。例如，在分解分数34时，因为12是比34小的最大埃及分数，所以只需要分

两次，就能得出

3

4

=

1

2

＋

1

4。按照这种分法（贪心法），你能画出把3块饼平均分给5个人的过程吗？第3题 找规律你能用“贪心法”将下面这些埃及分数拆分成两个埃及分数的和吗？“贪心”之智，化繁为简——埃及分数问题一组姜 华

77

The Horizon of Education12=1+ 1；13=1+ 1；14=1+ 1 。观察这些算式，你发现了什么？第4题 简便计算我们还可以将某些特别的埃及分数表示成两个埃及分数的差，例如，12=112´= 1-12，16= 123´=12-13，112=134´=13-14……运用这个规律，我们可以进行这样的简便计算： 1111261220+++=111112233445+++´´´´=（1-12）+（12-13）+（13-14）+（14-15）你能运用这样的规律计算“11612++111203042++”吗？【解析】第1题是理解埃及分数的基础，从图1中可以看出，4个人平均分3块饼时，先拿出其中的2块饼,将每块饼平均分成2份，一共平均分成了4份,于是每人可以先分得12块饼；再将剩下的1块饼平均分成4份,每人又可以分得14块饼。两次刚好分完，每人分得（1142+）块饼。解答第2题需要重点关注“用最少的次数分完”和“每次争取分到最多的饼”两点。因此，首先要保证每人都能分到1份，于是可以先将3块饼都平均分成2份，这样就有了6份，每人分得12块饼。再将剩下的12块饼平均分成5份，每人再分得110块饼。显然，把一个真分数表示为最少的埃及分数之和的形式，其“贪心策略”是选择真分数包含的最大埃及分数。以35为例，35＞12，12是第一次贪心选择的结果，因此，35块饼可以用（12＋110）块饼来表示。如果我们继续思考：如何找到真分数包含的最大埃及分数？可以设真分数为NM（M 除以N 的整数部分为P，余数为R），则有M=N×P+R，等式的两边同时除以N，因为余数R小于除数N，则有MN=P+RN＜P+1，推出NM＞11P+，11P+即为真分数NM包含的最大埃及分数。真分数减去最大埃及分数后,剩下的分数（或者化简之后）可能就是一个埃及分数；如果不是，则需要再次或多次进行贪心选择。解答第3题需要依据上述两题分饼的经验，用贪心法将一个埃及分数拆分成两个埃及分数的和。因为比12小的最大埃及分数是13，比13小的最大埃及分数是14，比14小的最大埃及分数是15，所以12=1136+，13=11412+，14=11520+，可以发现，每道算式中的3个分数的分母是有联系的，以第一道算式为例，2和3相邻且互质，6是2和3的最小公倍数。用字母表示这样的规律，即1a=111(1)aaa+++（a≠0）。解答第4题需要从第3题中获取经验，我们可以将12，14，16，112，120，130，142这些埃及分数表示成的1(1)aa+（a≠0）形式，并进一步表示成两个相邻埃及分数的差，即1(1)aa+= 1a-11a+ 。于是，有11612++111203042++＝123´+134´+145´+156´+167´=（12-13）+（13-14）+（14-15）+（15-16）+（16-17）=12- 17=514。【设计意图】类似“1111261220+++”的分数连加是苏教版小学数学五年级下册中较为常见的一类思维拓展题，学生可以根据异分母分数相加的运算法则，先通分再计算，也可以根据算式本身的特殊性，采用裂项相消法，将每个分数分裂成两个埃及分数之差，消去中间互为相反数的几项，得到首、尾两项的差，从而得出答案。裂项相消法把原本繁杂的分数连加计算，转化成了相对简单的减法算式。但是，“裂项相消法”是中学的数学学习 78智慧教学 2023年8

5. 贪心

狮子在树下抓到一只正在睡觉的兔子，正想饱餐一顿，却又看到一只鹿从旁边经过，又贪心地丢下兔子去追鹿。

狮子追了很远，可是还是让鹿逃跑了，于是又赶回树下，但野兔早已不见踪影了。狮子很懊恼地说：“我真是活该，因为贪心，反而两头落空。”

人生也常是如此。做许多事不能持之以恒，三心两意，一会儿想做这，一会儿又想做那，到时候也是两头落空。

-- 不能从失败中汲取教训的人，他们的成功之路是遥远的。

Greed

A lion caught a rabbit who was sleeping under a tree. While

going to take a hearty meal, the lion saw a deer passing by and

hunted it by leaving the rabbit out of greed. While planing to

take a hearty(good) meal, the lion saw a deer passing by. Then

he released the rabbit and hunted it greedily.

He chased for a long distant but failed to catch it. So he

came back to the tree in order to regain the rabbit. However, it

had already gone. “I get neither the rabbit nor the deer because I

am too greedy. I really deserved it!” he said ruefully.

Life is always like this story. Lacking of persistence and

贪心算法求解最优解问题

贪心算法是计算机科学领域中常用的一种算法。它常常被用来求解最优解问题，如背包问题、最小生成树问题、最短路径问题等。贪心算法解决最优解问题的基本思路是，每一步都选取当前状态下最优的解决方案，直到达到全局最优解。在这篇文章中，我们将为大家深入探讨贪心算法求解最优解问题的基本思路、算法复杂度和应用场景等方面的知识。

基本思路

贪心算法是一种基于贪心策略的算法。其核心思想是，每一步都采用当前最优策略，以期最终达到全局最优解。在贪心算法中，每个子问题的最优解一般都是由上一个子问题的最优解推导出来的。因此，关键在于如何找到最优解。

具体而言，贪心算法一般由三部分组成，分别为：状态、选择和判断。首先，需要明确当前问题的状态，即问题的规模和限制条件。然后，在当前的限制条件下，我们需要从可能的方案中选择出最优的方案，并把这个选择作为解的一部分。最后，需要判断选择是否符合问题的限制条件，是否达到全局最优解。

算法复杂度

在进行算法分析时，我们需要考虑算法的时间复杂度和空间复杂度。对于贪心算法而言，其时间复杂度一般是 O(nlogn) 或 O(n)

级别的，其中 n 表示问题的规模。这种效率在实际应用中表现出了很高的稳定性和效率。

应用场景

贪心算法通常应用于需要求解最优解问题的场景中。例如：

- 贪心算法可以用来求解背包问题。在背包问题中，我们需要在限定的空间内选取最有价值的物品装入背包中以努力获得最大的收益。在贪心策略下，我们只需要按单位重量价值从大到小的顺序进行选择，就可以得到最优解；

- 贪心算法也可以用来求解最小生成树问题。这个问题是指，在给定一个图的时候，我们需要选出一棵生成树，使得生成树上的所有边权之和最小。在此问题中，我们可以将图上的边权按大小排序，然后顺序选择边直至生成树。这样，我们可以得到与全局最优解很接近的解；

- 贪心算法还可以用来求解最短路径问题。在最短路径问题中，我们需要找到从一个节点到另一个节点的最短路径。在贪心策略下，我们只需要选择当前节点能到达的距离最短的节点，不断迭代即可。这样，我们就可以得到最短路径。

贪心算法几个经典例子c语言

1. 零钱兑换问题

题目描述：给定一些面额不同的硬币和一个总金额，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能够凑出总金额，返回 -1。

贪心策略：每次选择面额最大的硬币，直到凑出总金额或者无法再选择硬币为止。

C语言代码：

int coinChange(int* coins, int coinsSize, int amount){

int count = 0;

for(int i = coinsSize - 1; i >= 0; i--){

while(amount >= coins[i]){

amount -= coins[i];

count++;

}

}

return amount == 0 ? count : -1;

}

2. 活动选择问题

题目描述：有 n 个活动，每个活动都有一个开始时间和结束时间，选择一些活动使得它们不冲突，且能够参加的活动数最多。

贪心策略：每次选择结束时间最早的活动，直到所有活动都被选择或者无法再选择为止。 C语言代码：

typedef struct{

int start;

int end;

}Activity;

int cmp(const void* a, const void* b){

return ((Activity*)a)->end - ((Activity*)b)->end;

}

int maxActivities(Activity* activities, int n){

qsort(activities, n, sizeof(Activity), cmp);

int count = 1;

int end = activities[0].end;