量化投资学习笔记45——基本数据结构算法总结4 动态规划

发表于 | 分类于
| 字数统计: 1.1k | 阅读时长 ≈ 4

本章参考《算法图解》
动态规划先解决子问题，在逐步解决大问题。
仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。
动态规划的核心原理是利用已经计算的数据，避免重复计算。
动态规划的三大步骤：（这里参考了 https://zhuanlan.zhihu.com/p/91582909）
①定义数组元素的含义。dp[]
②找出数组元素之间的关系式。用之前的数据计算当前的数据，即用dp[n-1],dp[n-2]…dp[1]来推出dp[n]。
③找出初始值。即dp[1],dp[2]等。
这就是数学归纳法。
下面参考：https://www.zhihu.com/question/23995189/answer/613096905
动态规划问题的无后效性：给定某一阶段的状态，在这一阶段以后过程的发展不受这阶段之前的各段状态的影响。例子：斐波那契数列，f(n)=f(n-1)+f(n-2)，f(n)只与其之前的两个值有关，而与更前面的值无关。
最优子结构：大问题的最优解可以由小问题的最优解推出。
能用动态规划解决的问题：能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。
DP快的原因是自带剪枝的。即它舍弃了一大堆不可能成为最优解的答案，尽量缩小了可能解空间。

背包问题
解决方法参考这里:https://zhuanlan.zhihu.com/p/45279233

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
57
58
59
60
61
62
63
64
65
66
67
68
69
# coding:utf-8
# 动态规划

import numpy as np
import pandas as pd

# 物品类
class Dongxi:
    def __init__(self, name, weight, value):
        self.name = name
        self.weight = weight
        self.value = value
       
    def __str__(self):
        return self.name
       
       
# 背包类
class Bag:
    def __init__(self, volume):
        self.volume = volume
       
       
# 初始化，建立Dongxi类
def Initial(name, weight, value):
    list_of_thing = []
    for i in range(len(name)):
        list_of_thing.append(Dongxi(name[i], weight[i], value[i]))
    return list_of_thing
   
   
# 计算一个list里的对象的总价值
def value_sum(a_list):
    if type(a_list) != list:
        a_list = [a_list]
    return sum([x.value for x in a_list])
   

# 实施动态规划
def begin(list1, bag1, None_type):
    mat1 = pd.DataFrame(np.array([None_type]*(len(list1)+1)*(bag1.volume+1)).reshape(len(list1)+1, bag1.volume+1))
    for i in range(mat1.shape[0]):
        mat1.loc[i, :] = mat1.loc[i,:].apply(lambda x:list(set([x])))
       
    for i in range(1, mat1.shape[0]):
        for j in range(1, mat1.shape[1]):
            if  j < list1[i-1].weight:
                mat1.loc[i, j] = mat1.loc[i-1, j].copy()
            else:
                if value_sum(mat1.loc[i-1,j]) >= value_sum(mat1.loc[i-1, j-list1[i-1].weight]) + list1[i-1].value:
                    mat1.loc[i,j] = mat1.loc[i-1,j].copy()
                else:
                    mat1.loc[i,j] = mat1.loc[i-1, j-list1[i-1].weight].copy()
                    mat1.loc[i,j].append(list1[i-1])
                    if None_type in mat1.loc[i,j] and len(mat1.loc[i,j]) > 1:
                        mat1.loc[i,j].remove(None_type)
    return mat1
   
   
if __name__ == "__main__":
    # 动态规划解决背包问题
    name = ['a','b','c','d','e']
    weight = [2,2,6,5,4]
    value = [6,3,5,4,6]
    None_type = Dongxi('None_t',0,0)
    list1 = Initial(name,weight,value)
    bag1 = Bag(10)
    s1 = begin(list1,bag1,None_type)
    print(s1)

最大上升子序列问题，参考这里：https://www.zhihu.com/question/23995189/answer/305426560
给定一个数列：1,7,2,8,3,4 它的最长上升子数列为：1,2,3,4 长度为4。
分析，暴力穷举法是列举出所有的上升子序列，再找出最长的，时间复杂度为O(n!)
原问题求LIS(n)，现在需要找出LIS(n)和LIS(k)之间的关系，其中1<=k<=n。
人肉分析一下，LIS(k+1)要么等于LIS(k)，即增加的一项比前面的尾项小或相等，要么等于LIS(k)+1，即增加的一项比前面的尾项大。
所以原问题和子问题的关系为
LIS(n) = max(LIS(1),LIS(2),…,LIS(n-1)) + (A(n) > A(n-1)? 1: 0)
实现代码：参考 https://www.cnblogs.com/anzhengyu/p/11166708.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 动态规划求序列的最长子序列
def longest(nums):
    dp = []
    
    n = len(nums)
    max_ = 0
    for i in range(n):
        tmp = 1
        for j in range(0, i):
            if nums[j] < nums[i]:
                tmp = max(tmp, 1+dp[j])
        dp.append(tmp)
        if max_ < tmp:
            max_ = tmp
    return max_

我发文章的三个地方，欢迎大家在朋友圈等地方分享，欢迎点“在看”。
我的个人博客地址：https://zwdnet.github.io
我的知乎文章地址： https://www.zhihu.com/people/zhao-you-min/posts
我的微信个人订阅号：赵瑜敏的口腔医学学习园地

欢迎打赏！感谢支持！