贪心算法
介绍：贪心算法又称贪婪算法，是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的是在某种意义上的局部最优解。
贪心算法并不保证会得到最优解，但是在某些问题上贪心算法的解就是最优解。要会判断一个问题能否用贪心算法来计算。
例一：找零问题
问题：假设商店老板需要找零n元钱，钱币的面额有：100元、50元、20元、5元、1元，如何找零使得所需的钱币数量最少？
思路：为了找的钱币最少，从最大面额找，找不开就用比它小的找...
t = [100, 50, 20, 5, 1]
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))例二：背包问题
问题：一个小偷在某个商店发现有n个商品，第i个商品价值vi元，重wi千克。他希望拿走的价值尽量高，但他的背包最多只能容纳W千克的东西。他应该拿走哪些商品？
- 0-1背包：对于一个商品，小偷要么把它完整拿走，要么留下。不能只拿走一部分，或把一个商品拿走多次。(商品为金条)
- 分数背包：对于一个商品，小偷可以拿走其中任意一部分。(商品为金砂)
分数背包使用贪心算法没有问题，但是0-1背包不可以！
分数背包
goods = [(60, 10), (120, 30), (100, 20)] # 每个商品元组表示(价格, 重量)
goods.sort(key = lambda x:x[0]/x[1], reverse = True) # 按照单价排序
def fractional_backpack(goods, w):
m = [0 for _ in range(len(goods))]
total_v = 0
for i, (price, weight) in enumerate(goods):
if w >= weight:
m[i] = 1
w -= weight
total_v += price
else:
m[i] = w/weight
total_v += m[i] * price
w = 0
break
return m, total_v
print(fractional_backpack(goods, 50))例三：拼接最大数字问题 、
问题：有n个非负整数，将其按照字符串拼接的方式拼接为一个整数，如何拼接可以使得到的整数最大？
- 例：32、94、128、1286、6、71可以拼接的最大整数为：94716321286128
from functools import cmp_to_key
li = [32, 94, 128, 1286, 6, 71]
def xy_cmp(x, y):
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个活动，这些活动要占用同一片场地，而场地在某时刻只能供一个活动使用。
每个活动都有一个开始时间si和结束时间fi（题目中时间以整数表示），表示活动在[si, fi)区间占用场地。
问：安排那些活动能够使该场地举办的活动个数最多？
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| si | 1 | 3 | 0 | 5 | 3 | 5 | 6 | 8 | 8 | 2 | 12 |
| fi | 4 | 5 | 6 | 7 | 9 | 9 | 10 | 11 | 12 | 14 | 16 |
思路：最先结束的活动一定是最优解的一部分。
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))动态规划
介绍：是一种解决复杂问题的数学方法，通常用于优化问题。动态规划将问题分解为更小的子问题，通过解决这些子问题并将它们的解存储起来，最终得到原始问题的解。
思想：
- 最优子结构（递推式）
- 重复子问题
什么问题使用动态规划方法？
- 最优子结构
- 原问题的最优解中涉及多少个子问题
- 在确定最优解使用哪些子问题时，需要考虑多少种选择
- 重叠子问题
例一：斐波那契数列
# 子问题的重复计算
def fibnacci(n):
if n == 1 or n == 2:
return 1
else:
return fibnacci(n-1) + fibnacci(n-2)
# 无重复计算，存在列表中——动态规划(DP)
def fibnacci_no_recurision(n):
f = [0, 1, 1]
if n > 2:
for i in range(n-2):
num = f[-1] + f[-2]
f.append(num)
return f[-1]
print(fibnacci_no_recurision(100))例二：钢条切割问题
思路：
- 设长度为n的钢条切割后的最优收益值为
，可以得出递推式：
- 第一个参数
表示不切割
- 其他n-1个参数分别表示另外n-1种不同切割方案，对方案i=1,2,...,n-1
- 将钢条切割为长度为i和n-i两段
- 方案i的收益为切割两端的最优收益之和
- 考察所有的i，选择其中收益最大的方案
钢条切割问题满足最优子结构，比如长度为9要切为8和1，前面已经算了8的最佳情况，直接使用即可。
自顶向下递归实现
时间复杂度：
p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 27, 28, 30, 33, 36, 39, 40]
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 = 0
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, 15))
print(cut_rod_recurision_2(p, 15))自底向上动态规划实现
时间复杂度：
p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 27, 28, 30, 33, 36, 39, 40]
def cut_rod_dp(p, n):
r = [0]
for i in range(1, n+1):
res = 0
for j in range(1, i+1):
res = max(res, p[j] + r[i-j])
r.append(res)
return r[n]
print(cut_rod_dp(p, 9))重构解
同时输出最优解和最优切割方案
- 对于每个子问题，保存切割一次时左边切下的长度
def cut_rod_extend(p, n):
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 r[n], s
def cut_rod_solution(p, n):
r, s = cut_rod_extend(p, n)
ans = []
while n > 0:
ans.append(s[n])
n -= s[n]
return ans
print(cut_rod_solution(p, 9))例三：最长公共子序列实现
问题：一个序列的子序列是在该序列中删去若干元素后得到的序列。
例："ABCD"和"BDF"都是"ABCDEFG"的子序列
给定两个序列X和Y，求X和Y长度最大的公共子序列
返回最大公共子序列长度
def lcs_length(x, y):
m = len(x)
n = len(y)
# 创建一个二维数组来存储子问题的解
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 填充dp数组
for i in range(1, m + 1):
for j in range(1, n + 1):
if x[i - 1] == y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1 # i j 位置上的字符匹配时，来自与左上方
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# 从dp数组中找到最长公共子序列的长度
return dp[m][n]
# 测试
x = "abcde"
y = "ace"
print(lcs_length(x, y))
代码自己手动敲一遍理解更深哦！
