常见算法（1）之动态规划讲解

迷南。 2022-02-24 08:36 272阅读 0赞

动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。  
那么什么是动态规划呢，我们可以先来看一个例题  
（1）背包问题  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]  
1、先看简单算法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 3]  
注：这里用到公式Cn,0+Cn,1+…Cn,n=2^n  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][20190403111502709.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 5]  
下面开始填充网格：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 11]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 12]  
![在这里插入图片描述][20190403112034516.png]  
例1：  
现在添加一个2000美元的手机，背包还是4磅，计算出最优解  
基本题目如下：  
有4样商品，分别是  
（1）音响：4磅：3000美元  
（2）笔记本电脑：3磅：2000美元  
（3）iphone:1磅：2000 美元  
（4）吉他：1磅：1500美元  
只有一个4磅的背包，如何使商品价值最大  
下面是代码行：

#背包问题
        import numpy as np
        price=[3000,2000,2000,1500] #价格
        weight=[4,3,1,1] #对应的重量
        m=4 #背包重量
        n=4 #物品数
        x=np.zeros([n+1,m+1])
        for i in range(1,n+1):
            for j in range(1,m+1):
                if weight[i-1]<=j:
                    x[i][j]=max(x[i-1][j],x[i-1][j-weight[i-1]]+price[i-1])
                else:
                    x[i][j]=x[i-1][j]        
        print(x)    
        res=x
        
        def show(n,m,w,res):
        	print('最大价值为:',res[n][m])
        	item=[False for i in range(n)]
        	j=m
        	for i in range(n,0,-1):
        		if res[i][j]>res[i-1][j]: #代表取了这件物品
        			item[i]=True
        			j=j-weight[i]
        	for i in range(n):
        		if item[i]:
        			print('第',i,'个,',end='')
        show(n,m,weight,res)

结果：  
![在这里插入图片描述][20190403164006102.png]  
例2：假如你要去旅游，但是时间只有两天，这时你要列出了你将要旅游的单子，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 13]  
为了使你的评分最大化，你这时应该怎么选择最佳。你能通过已经规划好的动态规划的表格去反推你的行程吗？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 14]  
解析：设最优规划矩阵为a  
最终的路程为24->24的上一行的元素为22（24>22）,证明在第四行时选择了圣保罗大教堂（圣保罗大教堂）——>此时定位到a\[4\]\[4\]，减去圣保罗大教堂的需花费的天数（0.5），定位到a\[4\]\[3\]：16，比较a\[4\]\[3\]与a\[3\]\[3\],并没有变化，没有游览大英博物馆，  
——>定位a\[3\]\[3\],比较a\[3\]\[3\]与a\[2\]\[3\],数值增加了，证明去过英国国家美术馆（英国国家美术馆，圣保罗大教堂）——>a\[2\]\[3\]减去英国国家美术关的花费天数，定位到a\[2\]\[1\],比较a\[1\]\[1\]与a\[2\]\[1\],值没有变化则排除环球剧场——>最后比较a\[1\]\[1\]与0发现，值变大了，去过威斯敏特教堂。（英国国家美术馆，圣保罗大教堂,威斯敏特教堂）  
整个回溯完成

动态规划练习题：  
例1：走网格  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 15]

import numpy as np
        class Robot:
            def countWays(self, x, y):
                if x == 1 or y == 1:
                    return 1
                else:
                    dp = np.ones((x,y))
                    for i in range(1,x):
                        for j in range(1,y):
                               dp[i][j]=dp[i][j-1]+dp[i-1][j]
                return int(dp[-1][-1])

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70]: /images/20220224/cbcccd890c2c42bb8fe93340d6efccc4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 1]: /images/20220224/11801fd4416540c18e7dfe61537e0a6a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 2]: /images/20220224/52f8cd671310419d9a9130b1053fdec7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 3]: /images/20220224/0e55d6c74a2a4b84b7eb74c3f7515eeb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 4]: /images/20220224/107ed14de3fd470c84b7ce289dac98c8.png
[20190403111502709.png]: /images/20220224/0e57fbb1cf514a8b8f661d0c69f3303e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 5]: /images/20220224/d651962252204d15b4ef342cc632404c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 6]: /images/20220224/7f56d48352234a4dba5dfa7eca17119f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 7]: /images/20220224/7ad250f2d0fd4296997f4b885c3f73b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 8]: /images/20220224/d2376051a68e4869a8c3914b979389a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 9]: /images/20220224/1dc95bef2c6d4de8a42eea9e745a70bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 10]: /images/20220224/ba70400e5097454a8af674b6d47c21a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 11]: /images/20220224/84c6d1e647e446458a8360431efd4aed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 12]: /images/20220224/4606d3103e7b40ae89bf4f7efaddcfee.png
[20190403112034516.png]: /images/20220224/d8c80e68a8f44fb39ea4d8ce7f560c52.png
[20190403164006102.png]: /images/20220224/156793547bbc44ad8402dc21db84b39c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 13]: /images/20220224/2aac0568f852484092df17bab3b464db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 14]: /images/20220224/8cd17c1ba8d843d9b10d6d5f3ca3339f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTYxMTA0NQ_size_16_color_FFFFFF_t_70 15]: /images/20220224/9c1c2f5a12f541a8b5ebf00af8eddc8e.png