python数据结构教程 Day7

python数据结构教程 Day7

本节重点

1. 分治思想
2. 贪心策略
3. 动态规划

一、分治法

由递归三定律体现：

1. 基本结束条件，解决最小规模问题
2. 缩小规模，向基本结束条件演进
3. 调用自身来解决已缩小规模的相同问题

解决问题的典型策略：分而治之

问题解决依赖于若干缩小了规模的问题，汇总得到原问题的解。在排序、查找、遍历、求值中都有所应用。

二、贪心策略与最优化问题

首先这类策略往往解决的都是最优化问题，求最短路径？获得最小值、最大值的方案？等等。

示例：找零钱

设你为一家自动售货机厂家编程序，自动售货机要每次找给顾客最少数量硬币；

假设某次顾客投进$1纸币，买了ȼ37的东西，要找ȼ63，那么最少数量就是：2个quarter（ȼ25） 、1个dime（ȼ10）和3个penny（ȼ1），一共6个。

贪心策略指导我们进行如下的思考：

从最大面值的硬币开始，用尽量多的数量。如果仍有余额，再到下一最大面值的硬币，还用尽量多的数量，一直到penny（ȼ1）为止。因为我们每次都试图解决问题的尽量大的一部分，对应到兑换硬币问题，就是每次以最多数量的最大面值硬币来迅速减少找零面值。

但是当添加一种ȼ21的硬币时，贪心策略就失效了。实际上最优解是3个面值ȼ21的硬币！ ȼ63 = ȼ21*3，也就是说贪心策略是否有效依赖于具体的硬币体系。

我们需要重新来找一种肯定能找到最优解的方法！

暴力递归法

基本结束条件：需要兑换的找零，其面值正好等于某种硬币（1个即可）。由此，我们结合相同子问题即可获得硬币最优解的计算公式：

代码：

coinValueList = [1,5,10,25] # 已有的硬币
def recMC(coinValueList, change):
    '''
    这个算法的问题在于，寻找了过多的重复问题的解，
    对这个递归解法进行改进的关键就在于消除重复计算
    要优先记录最优解
    '''
    minCoins = change
    if change in coinValueList:
        return 1
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList, change - i)
            if numCoins < minCoins:
                minCoins = numCoins
    return minCoins

这个算法的问题在于，寻找了过多的重复问题的解

譬如对于一个找开26美分的问题来说：重复子问题找开15美分就遇到了三次，也就是说，这种暴力的递归在面对重复子问题时还要重新计算，明明是已经计算过的问题还要重新消耗计算资源，自然就慢很多。

改进：

记录中间结果，遇到子问题先查表，看有没有计算过，有的话就直接使用表中结果，没有再继续递归计算。

代码：

knowResults = [0] * 64
def recMC2(coinValueList, change, knownResults):
    minCoins = change
    if change in coinValueList: # 基本结束条件
        knownResults[change] = 1 # 记录最优解
        return 1
    elif knownResults[change] > 0:
        return knownResults[change] # 查表成功直接使用最优解
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC2(coinValueList, change - i, knownResults)
        if numCoins < minCoins:
            minCoins = numCoins
            knownResults[change] = minCoins # 记录子问题最优解
    return minCoins

这种处理方式是叫做“memoization（记忆化/函数值缓存）”的技术，其可提高了递归解法的性能。

三、动态规划

能够采用动态规划解决问题的特征：

问题最优解包含了子问题的最优解，能够列出状态转移方程。

1、找零问题（承上）

找零兑换的动态规划算法从最简单的“1分钱找零”的最优解开始，逐步递加上去，直到我们需要的找零钱数。在找零递加的过程中，设法保持每一分钱的递加都是最优解，一直加到求解找零钱数，自然得到最优解。

动态规划中最主要的思想是：从最简单情况开始到达所需找零的循环，其每一步都依靠以前的最优解来得到本步骤的最优解，直到得到答案。

以11分钱兑换问题为例：没有递归，因为子问题的答案都已经在表中了：

1. 首先减去1分硬币，剩下10分钱查表最优解是1
2. 然后减去5分硬币，剩下6分钱查表最优解是2
3. 最后减去10分硬币，剩下1分钱查表最优解是1

只需要在生成最优解列表同时跟踪记录所选择的那个硬币币值即可。

def dpMakeChange(coinValueList, change, minCoins, coinUsed):
    '''
    minCoins:记录子问题最少硬币数
    coinUsed:记录所选择硬币的币值
    '''
    # 从1分开始到change逐个计算最少硬币数
    for cents in range(change + 1):
        # 初始化为当前cents，最大值
        coinCount = cents
        newCoin = 1
        for j in [c for c in coinValueList if c <= cents]:
            if minCoins[cents - j] + 1 < coinCount:
                coinCount = minCoins[cents - j] + 1
                newCoin = j # 记录找开cents，用的最后一个硬币的面值
        minCoins[cents] = coinCount
        coinUsed[cents] = newCoin
    return minCoins[change] # 记录本步骤增加的1个硬币

# 回溯即可打印出最少硬币数的币值组合
def printCoins(coinUsed,change):
    coin = change
    while coin > 0:
        thisCoin = coinUsed[coin]
        print(thisCoin)
        coin = coin - thisCoin

动态规划的必要条件：

问题的最优解包含了更小规模子问题的最优解，最主要的思想是： 从最简单情况开始到达目标的循环，其每一步都依靠以前的最优解来得到本步骤的最优解，直到得到答案。

2、背包问题

面前有5件宝物，分别 有重量和价值，大盗的背包仅能负重20公斤，请问如何选择宝物，总价值最高？

item	weight	value
1	2	3
2	3	4
3	4	8
4	5	8
5	9	10

遵循动态规划思路：

前i(1<=i<=5)个宝物中，组合不超过W (1<=W<=20) 重量，得到的最大价值 m(i, W)应该是m(i-1, W)和m(i-1, W-Wi)+vi 两者最大值 我们从m(1, 1)开始计算到m(5, 20)

代码：

# 包重量
tr = [None, {'w':2, 'v':3}, {'w':3, 'v':4},
            {'w':4, 'v':8}, {'w':5, 'v':8},
            {'w':9, 'v':10}]
max_w = 20

# 构建动态规划表格
m = {(i,w):0 for i in range(len(tr))
                for w in range(max_w + 1)}

for i in range(1, len(tr)):
    for w in range(1, max_w+1):
        if tr[i]['w'] > w:
            m[(i,w)] = m[(i-1,w)]
        else:
            m[(i,w)] = max(m[(i-1,w)], m[(i-1, w-tr[i]['w'])] + tr[i]['v'])

print(m[(len(tr) - 1, max_w)]) 

核心：如果一个问题最优解包括规模更小相同问 题的最优解，就可以用动态规划来解决。“记忆化/函数值缓存”可以通过附加存储空间记录中间计算结果来有效减少重复计算。
上一篇：python数据结构教程 Day6