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))fori，money enumerate(T):m=N//money #除法向下舍入n=n% money #除法余数return m，n print (change (T，376)) # (3，1，1，1，1，0) 1.2背包问题常见的背包问题有整数背包问题和部分背包问题问题描述大致如下。
一个小偷在商店里发现了n种商品。第一件商品价值6元，重10公斤.他想把价值拿的越高越好，但是他的背包最多只能装W公斤。他应该拿走那些货物吗？
0-1背包:对于一件商品，小偷要么完全拿走，要么留着。不能只拿一部分，或者多次拿一个商品(商品是金条)。
分数背包:小偷可以拿走商品的任何部分。(商品为金沙)
示例：
贪婪算法能得到0-1背包和分数背包的最优解吗？为什么？显然，贪婪算法绝对可以得到分数背包的最优解。我们计算每个物品的单位重量值，然后按降序排列，然后开始取物品。只要它能装下所有这些东西，我们就能把它们都放进去。如果我们不能全部放进去，我们可以放一些进去，直到背包装满。
对于这个问题，显然0-1背包肯定不满意。即使偶尔可能，也不能满足所有0-1背包问题。0-1背包(又称整数背包问题)也可以分为两种：一种是每类物品的数量是有界的。一种是无限量，就是想有多少就有多少。这两个都不能用贪心策略。0-1背包是一个典型的第一整数背包问题。
得分背包代码实现：
#每个商品元组代表(价格，重量)商品=《60, 10》，(100，20)，(120，30) #我们需要先对商品进行排序，当然这里是排序后的商品. sort (key=lambda x3360x0/x1，Reverse=True)# w表示背包的容量def fractional _ backpack (goods，w) : # m表示有多少total _ v=0m=0 for _ in range(len(goods))for I，(prize，weight) in enumerate
bsp; w -= weight # m = 1 if w>= weight else weight / w else: m = w / weight total_v += m*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)) # 94716321286128补充：python cmp_to_key函数 下面学习一下Python中一个比较好用的模块，就是functools 中的 cmp_to_key函数，这里的 cmp_to_key就是在Python3中使用的，在Python2中就是 cmp函数。
它的具体作用就是比较函数。当然上面函数也可以写成下面形式：
def largestNumber(self, nums): from functools import cmp_to_key temp = list(map(str, nums)) temp.sort(key=cmp_to_key(lambda x, y: int(x + y) - int(y + x)), reverse=True) return ''.join(temp if temp<0> != '0' else '0') 上面函数有两个传入的参数 x, y，当 x>y 时返回1 等于时候返回0，否则返回-1。其实我最上面的函数比较明显。它在list的工作机制就是将列表中的元素去两两比较，当 cmp返回的时正数时交换两元素。
1.4 活动选择问题 假设有 n 个活动，这些活动要占用同一片场地，而场地在某时刻只能供一个活动使用。
每一个活动都有一个开始时间 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 = 1.5 最大子序和 求最大子数组之和的问题就是给定一个整数数组（数组元素有负有正），求其连续子数组之和的最大值。下面使用贪心算法逐个遍历。 代码如下： def maxSubarray(li): s_max, s_sum = 0, 0 for i in range(len(li)): s_sum += li s_max = max(s_max, s_sum) if s_sum < 0: s_sum = 0 return s_max 2，欧几里得算法――最大公约数2.1，最大公约数的定义 约数：如果整数 a 能被整数 b 整除，那么 a 叫做 b 的倍数，b 叫做 a 的约数。 最大公约数（Greatest Common Divisor）：给定两个整数 a, b，两个数的所有公共约数中的最大值即为最大公约数。 例如：12和16的最大公约数是 4 。 2.2，欧几里得算法如下： 欧几里得算法又称为辗转相除法，用于计算两个正整数a，b的最大公约数。 E:设两个正整数a, b，且已知a>bE1:令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>bdef 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算法的正确性，首先必须注意到以下结论： gcd(a,a)=a，也就是一个数和其自身的公约数仍是其自身。 gcd(ka,kb)=k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换。特殊地，当k=2时，说明两个偶数的最大公约数必然能被2整除。 当k与b互为质数，gcd(ka,b)=gcd(a,b)，也就是约掉两个数中只有其中一个含有的因子不影响最大公约数。特殊地，当k=2时，说明计算一个偶数和一个奇数的最大公约数时，可以先将偶数除以2。 代码如下： 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)
