一、贪心算法
贪心算法
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体
最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法并不保证会得到最优解，但是在某些问题上贪心算法的解就是最优解。
要会判断一个问题能否用贪心算法来计算。
''' 贪心算法例子1： 找零n元钱，面额100、 50、 20、 5、 1， 如何找零使所需钱币数量最少？ 算法思路： 每次都在剩余零钱中用大面值的去找 ''' def change(n): t = [100, 50, 20, 5, 1] #钱的面额，降序排列 m = [0, 0, 0, 0, 0] #每张面额的张数 for i, money in enumerate(t): m[i] = n // money n = n % money return m, n
''' 贪心算法例子2： 背包问题：商店有n个商品，背包最多只能装W千克的东西，怎么装使得背包中商品价值最大化？ 1.0-1背包：一个商品，只能完整拿走或者留下，一个商品只能拿走一次 2.分数背包：一个商品，可以拿走其中任意一部分，一个商品最多拿走一次 思考：对于0-1背包和分数背包，贪心算法是否都能得到最优解？为什么？ 思维实验结论：分数背包可以贪心来做；0-1背包不能贪心做。因为背包没装满 ''' from collections import namedtuple Good = namedtuple('Good', ['price', 'weight']) goods = [Good(60, 10), Good(120, 30), Good(100, 20)] # 按单位重量的价格降序排列 goods.sort(key=lambda g: g.price / g.weight, reverse=True) def f(goods, w): ''' :param goods: 商品列表 :param w: 背包限制重量 :return: ''' print(goods) m = [0 for _ in range(len(goods))] for i, g in enumerate(goods): if w >= g.weight: m[i] = 1 w -= g.weight else: m[i] = w / g.weight break return m m = f(goods, 50) print(m)
''' 有n个非负整数，按照字符串拼接的方式拼接为一个整数， 如何拼接可以使得到的整数最大？ 32,94,128,1286,6,71可以拼接的最大整数为 94716321286128 思考： 思路是比较最高位的数字，大的放前面，高位一样的，比较次高位，大的放前面 这样相当于是在进行从高到低的排序... 一个长一个短怎么处理，例如128和1286这种？ 这样的数排序的时候是排在一起的，只是不知道他们谁排前面而已。 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): ''' 两个数的大小比较规则 :param x: :param y: :return: ''' 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))
''' n个活动，都要占用同一片场地，而场地在某时刻只能供一个活动使用 每个活动在[s, f)之间占用场地。 每个活动时间冲突就不行，必须将时间错开 安排哪些活动可以使该场地举办活动个数最多？ 贪心策略：最先结束的活动一定是最优解的一部分 换句话说，最先结束的活动给剩下的活动留下来更多的时间，可以使开展的活动数量最多 证明：假设a是所有活动中最先结束的活动，b是最优解中最先结束的活动 如果a=b,结论成立。 如果a!=b, 则b的结束时间一定晚于a（因为a是所有里面最小的，而且a还不等于b） 如果用a替换掉最优解中的b，a一定不与最优解中的其他活动时间重叠（因为a比b早结束） 所以，替换后的解也是最优解 ''' 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): res = [a[0]] for i in range(1, len(a)): if a[i][0] >= res[-1][1]: # 如果当前活动的开始时间>=已安排的最后一个活动的结束时间，就不冲突 res.append(a[i]) return res ''' 思考：为什么遍历一遍就解决问题了？ 首先，待安排的活动数量是一定的，最多全部安排完，而且每个活动只能安排一次 按结束时间排序，就是早结束的优先安排，排在第一个的肯定是要安排的，因为是最早结束的 后面的活动，最好的情况是全部安排，但是有冲突的就不行了， 必须进行判断，虽然是最早结束的，但是有冲突的就只能看下一个了。 ''' print(activity_selection(activities))
贪心算法总结：
贪心算法能解决一部分“最优化”的问题，需要思考贪心策略：通过该贪心策略是否能得到最优解？
二、动态规划
动态规划：是一种算法思想，包括两方面
1、最优子结构（要解决这个问题，只需解决其子问题）：即递推式，例如fibnacci的递推式f(n)=f(n-1)+f(n-2)
2、重复子问题：例如f(5)的子问题是f(4),f(3),f(2),f(1)，子问题存起来，不需要重复计算
''' 使用递归和非递归的方法求斐波那契数列的第n项 1、2、3、4、5... 1、1、2、3、5、8、13、21、34、... ''' # 斐波那契的递归实现，进行了多次重复计算，效率低 def fibnacci(n): if n == 1 or n == 2: return 1 return fibnacci(n - 1) + fibnacci(n - 2) # 斐波那契的非递归实现，体现了动态规划的思想 def fibnacci_no_recurision(n): f = [1, 1] for i in range(n - 2): f.append(f[-1] + f[-2]) return f[-1] print(fibnacci_no_recurision(10)) ''' 思考：为什么递归效率低？ 因为fibnacci的递归进行了多次重复计算，例如： f(5) = f(4) + f(3) f(4) = f(3) + f(2) f(3) = f(2) + f(1) f(3) = f(2) + f(1) f(2) = 1 '''
动态规划--钢条切割问题解析：
钢条切割问题：
某公司出售钢条，出售价格与钢条长度之间的关系
---------表1：价格与钢条长度关系---------
长度 1 2 3 4 5 6 7 8 9 10
价格 1 5 8 9 10 17 17 20 24 30
----------------------------------
思维实验：
长度为4的钢条有几种切割方案？
第三种方案价格最高
-------------
切割方案 价格
4 9
1+3 9
2+2 10
3+1 9
1+1+2 7
1+2+1 7
2+1+1 7
1+1+1+1 4
--------------
思考：长度为n的钢条的不同切割方案有多少种？
一共2^n-1种方案，里面还有价格重复的方案，这样考虑时间复杂度就高的吓人了，显然不可取。
-----------表2：钢条长度i与最优价格r[i]关系----------
i 0 1 2 3 4 5 6 7 8 9 10
r[i] 0 1 5 8 10 13 17 18 22 25 30
--------------------------------------------------
长度为1：不切割，价格为1
长度为2：切割或不切割，5是最优价格
长度为3：切割或不切割，8是最优价格
长度为4：上面的8种切割方案，10是价格最高的
长度为5：13是最优价格，按照2+3这样切价格最高，这里不管2或者3具体怎么切，反正切成2最高价格为5，切成3最高价格为8
....可以发现点什么了，长度为6就是前面的两个长度的组合最高价格之和，就是动态规划思想的重复子问题，那么递推式是什么呢？？
递推式：
r[n] = max(Pn, r[1]+r[n-1],r[2]+r[n-2],...,r[n-1]+r[1])
（为什么是两个价格的组合，不是三个、四个...？
因为r[n-1],r[n-2]...它的切割不用再考虑，反正不管它如何切，最高价格已经在子问题中计算出来了）
---
p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
r=[0]
n=1 r[1] = max(P[1], )
n=2 max(P[2], r[1]+r[1])
n=3 max(P[3], r[1]+r[2], r[2]+r[1])
n=4 max(P[4], r[1]+r[3], r[2]+r[2], r[3]+r[1])
...
---
递推式说明：
1. Pn表示不切割
2. 切一刀，有n-1中不同的切法，分成两段，每段怎么切已经是子问题的最优解，子问题的最优解构成了整个问题的最优解
3. 在Pn和n-1中切法中，找最优的价格
最优子结构：
求规模为n的问题，可以分解成小的子问题，如果小问题的最优解能用来构造大问题的最优解的时候，称为最优子结构
钢条切割中，长度为9的钢条，不管切多少刀，考虑切一刀，切1和8，保证切1最大的钱，和切8最大的钱是该方案的最大的钱就行
钢条切割满足最优子结构：问题的最优解由相关子问题的最优解组合而成，这些子问题可以独立求解
钢条切割问题的递归式：
切一刀，左边切长度为i的，只对右边的一段继续切割
r[n]=max(P[i] + r[n-i]) 1<=i<=n i=n时表示不切割
n=1 r[1]=max(P[1] + r[0]) 1<=i<=1 i=[1,]
n=2 r[2]=max(P[i] + r[2-i]) 1<=i<=2 i=[1,2]
r[2]=max(P[1] + r[1])
r[2]=max(P[2] + r[0])
n=3 r[3]=max(P[i] + r[3-i]) 1<=i<=3 i=[1,3] 等价于：max(P[3], r[1]+r[2], r[2]+r[1])
r[3]=max(P[1] + r[2])
r[3]=max(P[2] + r[1])
r[3]=max(P[3] + r[0])
....
''' ---------表1：价格与钢条长度关系--------- 长度 1 2 3 4 5 6 7 8 9 10 价格 1 5 8 9 10 17 17 20 24 30 ---------------------------------- ''' p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30] def cut_rod_recurision_1(p, n): if n == 0: return 0 else: res = p[n] for i in range(1, n): res = max(res, cut_rod_recurision_1(p, i) + cut_rod_recurision_1(p, n - i)) return res def cut_rod_recurision_2(p, n): if n == 0: return 0 else: res = p[n] for i in range(1, n + 1): res = max(res, p[i] + cut_rod_recurision_2(p, n - i)) return res print(cut_rod_recurision_1(p, 9)) print(cut_rod_recurision_2(p, 9)) ''' 递归算法由于重复求解相同子问题，效率极低 动态规划的思想： 每个子问题只求解一次，保存求解结果 之后需要此问题时，只需查找保存的结果 '''
''' ---------表1：价格与钢条长度关系--------- 长度 1 2 3 4 5 6 7 8 9 10 价格 1 5 8 9 10 17 17 20 24 30 ---------------------------------- ''' p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30] def cut_rod_dp(p, n): ''' 钢条切割非递归实现，时间复杂度O(n²) :param p: 钢条长度和价格列表，下标表示长度 :param n: 给定钢条长度 :return: 钢条最高价格 ''' r = [0, ] for i in range(1, n+1): # 1 / 2 / 3 / ... / 11 i表示左边那段长度 res = 0 for j in range(1, i+1): # 1 / 1,2 / 1,2,3 / ... / 1,2,3,4,..11 res = max(res, p[j]+r[i-j]) r.append(res) return r[n]
def cut_rod_extend(p, n): ''' 钢条切割非递归实现，时间复杂度O(n²) :param p: 钢条长度和价格列表，下标表示长度 :param n: 给定钢条长度 :return: 钢条最高价格 ''' r = [0, ] # 钢条长度与最优方案价格的关系 s = [0, ] # 钢条长度与最优方案时左边固定切割长度的关系 for i in range(1, n+1): res_r = 0 # 最优方案的价格 res_s = 0 # 最优方案左边不切的长度 for j in range(1, i+1): if p[j]+r[i-j] > res_r: res_r = p[j]+r[i-j] res_s = j r.append(res_r) s.append(res_s) return s def cut_rod_solution(p, n): ''' 获取最优方案时钢条切割的各段长度 ''' s = cut_rod_extend(p, n) # s = [0, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10] solution = [] while n > 0: solution.append(s[n]) n -= s[n] return solution print(cut_rod_solution(p, 9))
234
23
最长公共子序列问题：
def lcs_length(x, y): m = len(x) n = len(y) c = [[0 for _ in range(n + 1)] for _ in range(m + 1)] for i in range(1, m+1): for j in range(1, n+1): if x[i-1] == y[j-1]: c[i][j] = c[i-1][j-1] + 1 else: c[i][j] = max(c[i-1][j], c[i][j-1]) # for _ in c: # print(_) return c[m][n] print(lcs_length("ABCBDAB", "BDCABA")) ''' 怎样求LCS字符串呢，先记录方向 ''' def lcs(x, y): m = len(x) n = len(y) # LCS长度矩阵 c = [[0 for _ in range(n + 1)] for _ in range(m + 1)] # LCS数据来自的方向矩阵 （1 左上方 2 上方 3 左方） b = [[0 for _ in range(n + 1)] for _ in range(m + 1)] for i in range(1, m+1): for j in range(1, n+1): if x[i-1] == y[j-1]: c[i][j] = c[i-1][j-1] + 1 b[i][j] = 1 elif c[i-1][j] > c[i][j-1]: c[i][j] = c[i-1][j] b[i][j] = 2 else: c[i][j] = c[i][j-1] b[i][j] = 3 # for _ in b: # print(_) return c[m][n], b def lcs_trackback(x, y): ''' 最长公共子序列可能有多个，只输出一个 ''' c, b = lcs(x, y) i = len(x) j = len(y) res = [] while i > 0 and j > 0: if b[i][j] == 1: # 来自左上方=>匹配 res.append((x[i-1])) i -= 1 j -= 1 elif b[i][j] == 2: #来自上方=>不匹配 i -= 1 else: # 来自左方 =>不匹配 j -= 1 return ''.join(reversed(res)) print(lcs_trackback("ABCBDAB", "BDCABA"))
欧几里得算法：求两个数的最大公约数
''' gcd(a,b)=gcd(b, a % b) gcd(60,21)=gcd(21,18)=gcd(18,3)=gcd(3,0)=3 ''' def gcd(a, b): if b == 0: return a else: return gcd(b, a % b) def gcd2(a, b): while b > 0: r = a % b a = b b = r return a print(gcd2(60,21))
23
4234
23