动态规划

发表于 | 分类于 | 阅读次数：

什么是动态规划

将问题分成小问题，并优先解决这些小问题. 动态规划先解决子问题，再逐步解决大问题.

举例: 费波那切数列

递归费波那切数列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
def fib(n):
    if n in (0, 1):
        return 1
    else:
        return fib(n-1) + fib(n-2)

def main():
    n = 20
    fib(n)


if __name__ == "__main__":
    main()

fib运行测试

费波那切数列递归树

可以看到上面费波那切数列的递归树存在反复计算子问题的步骤, 随着n的增大递归树会指数扩张.动态规划的优化思路就是去除子问题进而达到提升程序运行效率的目的.

动态规划费波那切数列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def fib(n, cache):
    if n in cache:
        return cache[n]
    elif n in (0, 1):
        cache[n] = 1
        return cache[n]
    else:
        # 存储子问题解
        cache[n] = fib(n-1, cache) + fib(n-2, cache)
        return cache[n]


def main():
    n = 20
    cache = {}
    fib(n, cache)


if __name__ == "__main__":
    main()

fib运行测试

上面的优化思路是使用了一个字典去存储子问题的解, 因此动态规划可以看成一种空间换时间的优化算法, 从两个测试的运行时间可以看出动态规划可以极大提高程序的运行效率.

举例: 背包问题

假设你是一个小偷背包中可装4磅的物品. 你可盗窃的商品如下

物品名 价值 重量
音响 3000 4
笔记本电脑 2000 3
吉他 1500 1

方法1: 穷举

可以使用尝试各种商品的组合, 并找出价值最高的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def select_item_by_mask(data, mask):
    r = [data[index] for (index, value) in enumerate(mask) if value == 1]
    return r


def int_to_mask(value, length):
    r = [ (value >> s) & 1 for s in range(length)]
    return r


def sum_value(data):
    r = sum((item[1]for item in data))
    return r


def sum_weight(data):
    r = sum((item[2]for item in data))
    return r


def backpack(data, pack_size):
    l = len(data)
    max_value = 0
    zuhe = []
    for i in range(2 ** l):
        # 生成 0 - 2^l的所有排列组合
        mask = int_to_mask(i, l)
        selected = select_item_by_mask(data, mask)
        total_value = sum_value(selected)
        total_weight = sum_weight(selected)
        if total_weight <= pack_size and total_value > max_value:
            max_value = total_value
            zuhe = selected
    return max_value, zuhe


def main():
    pack_size = 4
    name = ['吉他', '音箱', '笔记本']
    value = [1500, 3000, 2000]
    weight = [1, 4, 3]
    data = list(zip(name, value, weight))
    m = backpack(data, pack_size)
    print(m)


if __name__ == "__main__":
    main()

使用穷举可以解决问题, 但是随着n的增加复杂度会也会出现指数扩张(同费波那切数列未优化前).

方法2: 动态规划

把背包分解成小背包, 行为待选的物品(n), 行为子背包的大小(w), 这时初始化了一个n*m的矩阵用于存放子问题的解.

物品 1 2 3 4
吉他
音响
笔记本电脑

矩阵用matrix来表示,行下标用i表示, 列下标用j表示.

当i=0时, 在matrix[0]行时只能选择背包中只能选择吉, 矩阵如下

物品 1 2 3 4
吉他 (1500, 1) (1500, 1) (1500, 1) (1500, 1)
音响
笔记本电脑

当i=1时, 在matrix[1]行可以选择吉他和音箱,因为音箱重量为4所以1-3背包存放不下, 只能继承上一行的数值.

物品 1 2 3 4
吉他 (1500, 1) (1500, 1) (1500, 1) (1500, 1)
音响 (1500, 1) (1500, 1) (1500, 1) (3000, 4)
笔记本电脑

当i=2时, 在matrix[2]行可以选择三个物品, 由于1-2背包依旧只能存放吉他因此还继承上一行的数值, 但3背包可以存放价值为2000的笔记本电脑, 这样3背包存放的最大价值为2000.

物品 1 2 3 4
吉他 (1500, 1) (1500, 1) (1500, 1) (1500, 1)
音响 (1500, 1) (1500, 1) (1500, 1) (3000, 4)
笔记本电脑 (1500, 1) (1500, 1) (2000, 3)

这时在填充matrix[2][3]时存在时可以选择(笔记本+剩余1磅子背包)或者是(音箱)

1
2
3000  <  (2000   + 1500)
 音箱    笔记本电脑   吉他

得到最终矩阵为

物品 1 2 3 4
吉他 (1500, 1) (1500, 1) (1500, 1) (1500, 1)
音响 (1500, 1) (1500, 1) (1500, 1) (3000, 4)
笔记本电脑 (1500, 1) (1500, 1) (2000, 3) (3500,4)

上述的计算过程可以推导出一个方程, matrix中的所有元素都满足这个方程

1
2
3
4
5
i=0
matrix[0][j]= items[0] if items.weight <= 子背包重量 else [0, 0]
# 能取到的
i>0
matrix[i][j] = max(cell[i-1][j], 当前商品价值 + cell[i-1][j-当前商品重量])

上述方程称为状态转移方程, 推导出状态转移方程动态规划基本也就掌握了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def log_matrix(matrix):
    for line in matrix:
        print(line)
    print()


def init_matrix(data, pack_size):
    matrix = [[[0, 0] for i in range(pack_size)] for _ in data]
    return matrix


def backpack(data, pack_size):
    # 状态转移方程
    # cell[i][j] = max(cell[i-1][j], i + cell[i-1][j - 当前商品重量]
    matrix = init_matrix(data, pack_size)
    cell = matrix
    for i, line in enumerate(matrix):
        current_goods = data[i]
        print("out current goods: ",current_goods)
        value = current_goods[1]
        weight = current_goods[2]
        for j, _ in enumerate(line):
            child_backpack_size = j + 1
            if i == 0:
                if weight <= child_backpack_size:
                    cell[i][j][0] = value
                    cell[i][j][1] = weight
            else:
                a = cell[i-1][j]
                # b = value + cell
                if weight > child_backpack_size:
                    b = [0, 0]
                elif weight == child_backpack_size:
                    b = [value, weight]
                else:
                    mod = cell[i-1][j - weight]
                    value = mod[0] + value
                    weight = mod[1] + weight
                    b = [value, weight]
                cell[i][j] = max(a, b, key=lambda x: x[0])
        log_matrix(cell)
    return cell[-1][-1]


def main():
    pack_size = 4
    name = ['吉他', '音箱', '笔记本']
    value = [1500, 3000, 2000]
    weight = [1, 4, 3]
    data = list(zip(name, value, weight))
    m = backpack(data, pack_size)
    print(m)


if __name__ == "__main__":
    main()

作业: 杨辉三角问题

杨辉三角中每个位置随意填写数字, 经过某个数字只能达到下面一层相邻的两个数字.
假设你站在第一层, 往下移动, 我们把wids到最底层经过的所有数字之和, 定义为
路径的长度. 请求出从最高层移动到最底层的最短路径长度.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 杨辉三角
def triangle(triangle):
    # triangle = [
    #   [2],
    #  [3,4],
    #  [6,5,7],
    # [4,1,8,3]
    # ]
    """
    杨辉三角移动的关系
               tringle[i][j]
    tringle[i+1][j]   tringle[i+1][j+1]

    状态转移方程
    dp = [0] * (len(triangle) + 1)
    dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
    """
    pass

参考