第4课 贪心算法¶
这节课我们学习一种特殊的算法，首先看下面这么一个题目
题目：找零钱¶
描述
商店售货员希望用数目最小的硬币找零。假设提供了数目不同的面值为25美分、10美分、5美分和1美分的硬币。
输入描述
输入一个整数\(n (1 \le n \le 100)\)表示以美分记的钱数。
输出描述
按格式输出四种零钱各需要多少个（注意单复数）。详细见输出案例
样例输入#1
98
Change: 3 Quarters, 2 Dimes, 0 Nickel, 3 Cents
样例输入#2
67
样例输出#2
Change: 2 Quarters, 1 Dime, 1 Nickel, 2 Cents
找出所有可能并比较！¶
这是一道非常实用的题目。题目中描述的情景在生活中时常出现，小伙伴们通过阅读题目，一定会有一些思路了。前面我们学习过穷举法， 相信小伙伴们肯定已经有以下的思路：
- 把所有的可能的硬币组合都尝试一遍，当硬币组合成目标值
n时，记录下总硬币数和其对应的硬币组合。 - 比较总硬币数，其中最小的即为题目所解。
根据以上思路，我们可以很快写出如下的程序框架：
import sys
for line in sys.stdin:
n = int(line)
min_nb_coins = ___________
nb_quarters = 0
nb_dimes = 0
nb_nickels = 0
nb_cents = 0
for i in range(______):
for j in range(_________):
for k in range(__________):
for l in range(___________):
if _____________ and ____________:
min_nb_coins = _____________
nb_quarters = ___________
nb_dimes = ___________
nb_nickes = ___________
nb_cents = ___________
print(_______________)
在穷举法的框架中，下划线的部分是这个程序中最关键的地方，接下来我们要一一确定。不过在开始之前，我们先简单快速地把题目要求的输入输出相关问题解决了。
-
首先注意到：题目中输入的样例表明，输入中每行有一个整数，是要求解的题目中的
n值。所以在python中可以使用for line in sys.stdin方法读入，但是不要忘记默认读入是字符串，我们需要转换为整型数值。 -
题目中特别嘱咐了要注意输出时的硬币种类的单复数，所以这里需要借助字符串的格式化方法：把单复数产生时的字符
"s"也考虑到字符串的格式化中，很快可以写出如下的语句：
print("Change: {} Quarter{}, {} Dime{}, {} Nickel{}, {} Cent{}".\
format( nb_quarters, "s" if nb_quarters > 1 else "",
nb_dimes, "s" if nb_dimes > 1 else "" ,
nb_nickels, "s" if nb_nickels > 1 else "",
nb_cents, "s" if nb_cents> 1 else "" ))
输入输出的问题解决以后，接下来确定穷举法需要穷举的范围（即所有可能的解）。我们需要遍历每种硬币值可能的数目，那么每种币值的硬币最大可能的数目会发生在什么情况下呢？对的，是我们仅仅完全使用某一币值的硬币来找零钱的时候。所以一种面值为value的硬币的取值范围为：0 - floor(n/value)，注意其中的floor函数为向下取整。下面可以确定循环的范围：
for i in range(n // 25 + 1):
for j in range(n // 10 + 1):
for k in range(n // 5 + 1):
for l in range(n + 1):
目前为止，确定了每种币值可能的数目。
注意，Python中
range并不包含本身,需要加1。另外，在求硬币数目时需要用整除，即向下取整的方法。
最后，穷举法中最重要是写出满足题目条件的条件判断式。
if i * 25 + j * 10 + k * 5 + l == amount and (i + j + k + l ) < min_nb_coins:
nb_quarters = i
nb_dimes = j
nb_nickels = k
nb_cents = l
至此，我们使用穷举法解出了这题。那小伙伴们能不能计算一下，穷举法的计算复杂度呢？我们可以粗略估计一下，每种硬币的循环次数是\(\frac{n}{coin}\), 那么四种硬币就大概是\(\frac{n^4}{25 * 10 * 5 * 1}\)，此时本题中穷举法的时间复杂度是\(O(n^4)\)。并且随着币值种类m的增加，计算复杂度会更高，为\(O(n^m)\)次。
贪心算法¶
上面的算法，我们充分应用了计算机的优势，通过计算机强大的运算力，暴力地计算出每一种可能，并从中筛选出符合目标条件的值。但是在生活中我们并不会采用如此愚蠢的方法。我们可以仔细回想一下，人类在找零钱的时候，或者说你平常在找零钱时脑海是一个什么样的思考过程？
对，我们可能会从最大币值的开始找起。当剩余的钱不足最大币值的钱币时，我们考虑用第二大币值的钱币，然后以此类推。比如，在需要找零钱31元时，我们会先使用25元硬币，剩下的6元，我们再使用1个5元硬币，接着再使用1个1元硬币。 是的，我们人类在大多数时候会将问题分解成每一个小问题，然后在每个小问题中，尽量选择最优的可能（此处是采用最大的面值，所以是最少的硬币数）。所以我们把这种将一个问题分成若干子问题解决，并且在每个子问题中选择最优的可能继续下去的方法叫做贪心算法。
了解到贪心算法后，再根据我们平常找零钱时的思路，我们可以尝试使用贪心算法写出如下代码：
import sys
for line in sys.stdin
n = int(line)
nb_quarters = 0
nb_dimes = 0
nb_nickels = 0
nb_cents = 0
while n >= 25:
n -= 25
nb_quarters += 1
while n >= 10:
n -= 10
nb_dimes += 1
while n >= 5:
n -= 5
nb_nickels += 1
while n >= 1:
n -= 1
nb_cents += 1
# Omitted.
# print(....)
敏感的同学可以注意到，我们每次找硬币时，都是需要将目前所剩下的零钱数中减去最大币值。实际上，这就是一个除法的运算。所以我们没有必要使用循环去做减法。只要构造一下从大到小的币值列表，并且按照这个顺序，用需要找的零钱去除以当钱币值，得到的商即为该币值钱币数，余数留做下一面值所需要找的零钱数。 所以我们把程序稍微修改一下，可以得到一个非常简洁的程序:
import sys
for line in sys.stdin
n = int(line)
# 从大到小排列，这样符合贪心算法的原则
coins = [25, 10, 5, 1]
# 记录每种币值的钱币数
nb = [0, 0, 0, 0]
i = 0
while n != 0:
nb[i] = n // coins[i]
n = n % coins[i]
i += 1
# Omitted.
# print(....)
这个程序不仅非常简洁易懂，而且还很容易扩展，我们随时可以增加不同的硬币值，以方便不同国家的人民使用（hoho)。
计算复杂度¶
那我们可以分析一下计算复杂度，显而易见，程序最多只会进行币值种类数m次循环, 所以其时间复杂度是\(O(1)\)，即只要币值种类确定，不管需要找的零钱数n为多少，则只需要常数的时间即可解决。
所以可见，人类还是非常强大的，尽管我们的计算速度不够快，但是冥冥之中，我们本身就具有一种非常强大的能力，天生就能够用很快（不是最优）的方法去解决。那我为什么没有说人类用最优的方法去解决的呢？接下来请你看一个实验，请你把币值列表中的[25, 10, 5, 1]中的5删去，再运行程序，输入30元零钱,看看我们的程序的解是如何？没错是1 Quarters, 5 Cents, 共需要6个硬币。但是聪明的你很快就发现，我们不是用3 Dimes就能够完成找零了吗？
没错，要注意，贪心算法在每一小步都采用最优的选择，但是它不并能够保证你最后的结果也是最优的（全局最优）！贪心算法一般只能在一些情况下才能达到全局最优。所以你知道，每个国家币值的设定是经过精心考虑的！！！
好，那我们怎么才能得到任意币值种类下的最少硬币找零解呢？所以我们得把视线又拉回到“穷举法”上，因为穷举法的特点就是：解一定是最优的，但是复杂度非常高。我们要想办法把穷举法的复杂度降低，那不是就能平衡一下。
作业¶
请完成C006, C007两题