python常用算法（6）——贪心算法，欧几里得算法
lixiaotao 2019-10-28
1，贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的的时在某种意义上的局部最优解。
贪心算法并不保证会得到最优解，但是在某些问题上贪心算法的解就是最优解。要会判断一个问题能否用贪心算法来计算。贪心算法和其他算法比较有明显的区别，动态规划每次都是综合所有问题的子问题的解得到当前的最优解（全局最优解），而不是贪心地选择；回溯法是尝试选择一条路，如果选择错了的话可以“反悔”，也就是回过头来重新选择其他的试试。
1.1 找零问题
假设商店老板需要找零 n 元钱，钱币的面额有100元，50元，20元，5元，1元，如何找零使得所需钱币的数量最少？（注意：没有10元的面额）
那要是找376元零钱呢？ 100*3+50*1+20*1+5*1+1*1=375
代码如下：
# t表示商店有的零钱的面额
t = [100, 50, 20, 5, 1]
# n 表示n元钱
def change(t, n):
m = [0 for _ in range(len(t))]
for i, money in enumerate(t):
m[i] = n // money # 除法向下取整
n = n % money # 除法取余
return m, n
print(change(t, 376)) # ([3, 1, 1, 1, 1], 0)1.2 背包问题
常见的背包问题有整数背包和部分背包问题。那问题的描述大致是这样的。
一个小偷在某个商店发现有 n 个商品，第 i 个商品价值 Vi元，重 Wi 千克。他希望拿走的价值尽量高，但他的背包最多只能容纳W千克的东西。他应该拿走那些商品？
0-1背包：对于一个商品，小偷要么把他完整拿走，要么留下。不能只拿走一部分，或把一个商品拿走多次（商品为金条）
分数背包：对于一个商品，小偷可以拿走其中任意一部分。（商品为金砂）
举例：
对于 0-1 背包 和 分数背包，贪心算法是否都能得到最优解？为什么？
显然，贪心算法对于分数背包肯定能得到最优解，我们计算每个物品的单位重量的价值，然后将他们降序排序，接着开始拿物品，只要装得下全部的该类物品那么就可以全装进去，如果不能全部装下就装部分进去直到背包装满为止。
而对于此问题来说，显然0-1背包肯定装不满。即使偶然可以，但是也不能满足所有0-1背包问题。0-1背包（又叫整数背包问题）还可以分为两种：一种是每类物品数量都是有限的（bounded）。一种是数量无限（unbounded），也就是你想要的多少有多少，这两种都不能使用贪心策略。0-1背包是典型的第一种整数背包问题。
分数背包代码实现：
# 每个商品元组表示（价格，重量）
goods = [(60, 10), (100, 20), (120, 30)]
# 我们需要对商品首先进行排序，当然这里是排好序的
goods.sort(key=lambda x: x[0]/x[1], reverse=True)
# w 表示背包的容量
def fractional_backpack(goods, w):
# m 表示每个商品拿走多少个
total_v = 0
m = [0 for _ in range(len(goods))]
for i, (prize, weight) in enumerate(goods):
if w >= weight:
m[i] = 1
total_v += prize
w -= weight
# m[i] = 1 if w>= weight else weight / w
else:
m[i] = w / weight
total_v += m[i]*prize
w = 0
break
return m, total_v
res1, res2 = fractional_backpack(goods, 50)
print(res1, res2) # [1, 1, 0.6666666666666666]1.3 拼接最大数字问题
有 n 个非负数，将其按照字符串拼接的方式拼接为一个整数。如何拼接可以使得得到的整数最大？
例如：32， 94， 128， 1286， 6， 71 可以拼接成的最大整数为 94716321286128.
注意1：字符串比较数字大小和整数比较数字大小不一样！！！ 字符串比较大小就是首先看第一位，大的就大，可是一个字符串长，一个字符串短如何比较呢？比如128和1286比较
思路如下：
# 简单的：当两个等位数相比较 a = ‘96‘ b = ‘97‘ a + b if a > b else b + a # 当出现了下面的不等位数相比较，如何使用贪心算法呢？ # 我们转化思路，拼接字符串，比较结果 a = ‘128‘ b = ‘1286‘ # 字符串相加 a + b = ‘1281286‘ b + a = ‘1286128‘ a + b if a + b > b + a else b + a
数字拼接代码如下：
from functools import cmp_to_key
li = [32, 94, 128, 1286, 6, 71]
def xy_cmp(x, y):
# 其中1表示x>y，-1,0同理
if x+y < y+x:
return 1
elif x+y > y+x:
return -1
else:
return 0
def number_join(li):
li = list(map(str, li))
li.sort(key=cmp_to_key(xy_cmp))
return "".join(li)
print(number_join(li)) # 947163212861281.4 活动选择问题
假设有 n 个活动，这些活动要占用同一片场地，而场地在某时刻只能供一个活动使用。
每一个活动都有一个开始时间 Si 和结束时间 Fi （题目中时间以整数表示）表示活动在 [Si, fi) 区间占用场地。（注意：左开右闭）
问：安排哪些活动能够使该场地举办的活动的个数最多？
贪心结论：最先结束的活动一定是最优解的一部分。
证明：假设 a 是所有活动中最先结束的活动，b是最优解中最先结束的活动。
如果 a=b，结论成立
如果 a!=b，则 b 的结束时间一定晚于 a 的结束时间，则此时用 a 替换掉最优解中的 b ，a 一定不与最优解中的其他活动时间重叠，因此替换后的解也是最优解。
代码如下：
# 一个元组表示一个活动，（开始时间，结束时间）
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11),
(8, 12), (2, 14), (12, 16)]
# 保证活动是按照结束时间排好序,我们可以自己先排序
activities.sort(key=lambda x:x[1])
def activity_selection(a):
# 首先a[0] 肯定是最早结束的
res = [a[0]]
for i in range(1, len(a)):
if a[i][0] >= res[-1][1]: # 当前活动的开始时间小于等于最后一个入选活动的结束时间
# 不冲突
res.append(a[i])
return res
res = activity_selection(activities)
print(res)1.5 最大子序和
求最大子数组之和的问题就是给定一个整数数组（数组元素有负有正），求其连续子数组之和的最大值。下面使用贪心算法逐个遍历。
代码如下：
def maxSubarray(li):
s_max, s_sum = 0, 0
for i in range(len(li)):
s_sum += li[i]
s_max = max(s_max, s_sum)
if s_sum < 0:
s_sum = 0
return s_max2，欧几里得算法——最大公约数
2.1，最大公约数的定义
约数：如果整数 a 能被整数 b 整除，那么 a 叫做 b 的倍数，b 叫做 a 的约数。
最大公约数（Greatest Common Divisor）：给定两个整数 a, b，两个数的所有公共约数中的最大值即为最大公约数。
例如：12和16的最大公约数是 4 。
2.2，欧几里得算法如下：
欧几里得算法又称为辗转相除法，用于计算两个正整数a，b的最大公约数。
- E:设两个正整数a, b，且已知a>b
- E1:令r = a%b(‘%‘代表取余)
- E2:若r=0(即n整除m)，结束运算，n即为结果
- E3:否则令a=b，b=r，并返回步骤E1
欧几里得算法运用了这样一个等价式（设 gcd(a, b)代表 a 和 b 的最大公约数，mod()代表取余运算或模运算）则：
gcd(a, b) = gcd(b, a mod b ) = gcd(b, a%b)
也就是说 m , n 的最大公约数等于他们相除余数（r）和 n 的最大公约数。
例如：gcd(60, 21) = gcd(21, 18) = gcd(18, 3) = gcd(3, 0) = 3
意思就是 60对21取余18，同理21对18余3，18对3取余0，所以3为两个数的最大公约数。
2.3，证明欧几里得公式
我们的证明分为两步。第一步，证明gcd(a, b)是b, a%b 的一个公约数。第二步，证明这个公约数是最大的。
1，证明gcd(a, b)是b, a%b 的一个公约数
1，因为任意两个正整数都有最大公因数，设为 d。
2，将 a , b 分别用最大公因数 d 来表示为 a = k1*d b = k2*d （k1，k2是两个常数）
3，设 a = k*b + c （也就是a 除以 b 商 k 余 c），然后把a = k1*d b = k2*d 两个式子中的 a，b代入式子，得到：
c = a - k*b = k1*d - k * k2 * d，然后再提取公因数 d，得到 c = (k1 - k2 * k)*d，这就说明，c也就是 a%b有 d 这个约数，因为开始我们设 任意两个数都有最大公约数d，所以 gcd(a, b) 是 b， a%b 的一个公约数。
4，由此可以得到 c 是最大公因数 d 的倍数，得证：gcd(a, b) = gcd(b, a mod b)。所以以此类推，可以将 m n中较大的数用较小的数的余数 r 替换，实现了降维，所以有了E3的步骤。
2，证明我们求出来的公约数是最大的
1，数学是一门严谨的学科，我们需要严谨的正面，我们知道 c(a%b) = k1*d - k * k2 * d b = k2*d，所以我们只需要证明k1-k*k2, k2互质即可。
2，这里可以用到反证法，我们假设 k1 - k*k2 = q*t k2=p*t，再讲这个k1 代入最开始的 a=k1*d ，得到 a=(q*t + k*k2)*d，再利用乘法分配律得到： a = q*t*d + k*k2*d，这时候我们发现，k2*d就是b，将其代入，得到 a=q*t*d + b*d
3，我们在将k2 = p*t代入开始的b = k2*d,得到b = p*t*d，再把这个式子代到a = q*t*d+b*d.得到了：a = q*t*d+p*t*d.提取公因数：a=(q+p)*t*d
4，再和b=p*t*d比较，发现他们的最大公因数变成了t*d和开始矛盾，所以假设不成立，反证成功！
2.4，如何计算最大公约数？
1，欧几里得：辗转相除法（欧几里得算法）
2，《九章算术》：更相减损术
代码如下：
# 递归法：保证a>b
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 递推法
def gcd1(a, b):
if a < b:
a, b = b, a
while b > 0:
r = a % b
a = b
b = r
return a因为这是一个伪递归，所以时间复杂度不高。
2.5，应用：实现分数计算
利用欧几里得算法实现一个分数类，支持分数的四则运算。
代码如下：
# _*_coding:utf-8_*_
class Fraction:
def __init__(self, a, b):
self.a = a
self.b = b
x = self.gcd(a, b)
self.a /= x
self.b /= x
# 最大公约数
def gcd(self, a, b):
while b > 0:
r = a % b
a = b
b = r
return a
# 最小公倍数
def zgs(self, a, b):
# 12 16 -> 4
# 3 * 4 * 4=48
x = self.gcd(a, b)
return (a * b / x)
# 加法的内置方法
def __add__(self, other):
# 1/12 + 1/20
a = self.a
b = self.b
c = other.a
d = other.b
fenmu = self.zgs(b, d)
femzi = a * (fenmu / b) + c * (fenmu / d)
return Fraction(femzi, fenmu)
def __str__(self):
return "%d/%d" % (self.a, self.b)
f = Fraction(30, 16)
print(f)2.7 欧几里得算法的缺点
欧几里得算法是计算两个数最大公约数的传统算法，无论从理论还是实际效率上都是很好地。但是却有一个致命的缺陷，这个缺陷在素数比较小的时候一般是感受不到的，只有在大素数时才会显现出来。
一般实际应用中的整数很少会超过64位（当然现在已经允许128位），对于这样的整数，计算两个数之间的模很简单。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。
由J. Stein 1961年提出的Stein算法很好的解决了欧几里德算法中的这个缺陷，Stein算法只有整数的移位和加减法，为了说明Stein算法的正确性，首先必须注意到以下结论：
代码如下：
def gcd_Stein(a, b):
if a < b:
a, b = b, a
if (0 == b):
return a
if a % 2 == 0 and b % 2 == 0:
return 2 * gcd_Stein(a/2, b/2)
if a % 2 == 0:
return gcd_Stein(a / 2, b)
if b % 2 == 0:
return gcd_Stein(a, b / 2)
return gcd_Stein((a + b) / 2, (a - b) / 2)参考文献：https://www.cnblogs.com/jason2003/p/9797750.html
https://www.cnblogs.com/Dragon5/p/6401596.html
