算法快学笔记（十六）：动态规划

「爱情、让人受尽委屈。」 2023-06-13 03:30 92阅读 0赞

# 1. 介绍 #

前文提到，对于背包问题与旅行商问题，计算的复杂度是随着计算数据的增加呈现指数级增长的，贪婪算法算可以处理，但得到的并不是最优解。

动态规划的主要思路是先解决子问题，在逐步解决大问题。本文将通过两个例子介绍动态规划的推算思路。

# 2. 背包问题 #

## 2.1 思路 ##

通过动态规划方法解决背包问题的流程如下：

1.  准备一个表格，商品作为Y轴，背包重量作为x轴
2.  使用下面的公式算出价格且更新到表格里  
    ![在这里插入图片描述][20191113171125313.jpg]
3.  使用方法2，逐行填充表格，直到将表格填满。

## 2.2 推算过程 ##

用于推算的数据如下：

1.  小偷的背包可以放4KG的物品
2.  可偷物品的价格，重量如下：

详细推算过程如下:

1.  初始化表格如下

1.  吉他是第一个商品，且重量只有1kg,则对于不同大小的背包而言都可以放得下，所以第一行的值都为1500

1.  音响是第二个商品，对于1,2,3三个背包都放不下，所以能放的物品价值还是1500,第四个背包可以放下，使前面提到的公式推导一下。

*  CELL\[1\]\[4\]=1500
 *  当前价值+剩余空间价值=3000+0(没有剩余的空间，所以剩余价值为0)  
    通过上面的推算，可知音响这行最后一格的值为3000

1.  看下笔记本，前两个背包都放不下，从第三个开始。第三个背包放完笔记本后价值为2000,且比CELL\[2,3\]要大，所以该值更新为2000

再来看笔记本的最后一格,比较下面的值：

*  CELL\[2\]\[4\]=3000
 *  2000(笔记本价格)+1500(剩余空间的最大价值)=3500

由上可得出笔记本第四格的价值应该是3500

1.  手机的重量为1kg.且比吉他的价格要贵，所以第一格替换成手机的价格

对于第二格，比较下面的值：

*  CELL\[3\]\[2\]=1500
 *  2000(笔记本价格)+1500(剩余空间的最大价值，C\[3,1\])=3500

由上可得出手机第二格的价值应该是3500

第三格的推算过程与第二格类似，值同样为3500.

对于第四格，比较下面的值：

*  CELL\[3\]\[4\]=3500
 *  2000(笔记本价格)+2000(剩余空间的最大价值，C\[3,3\])=4000

由上可得出手机第四格的价值应该是4000

最终可得知，小偷最多可偷4000元的商品，且偷的商品是手机+笔记本电脑。

## 2.4 其他注意事项 ##

1.  最终的结果和表格中商品的顺序没有关系
2.  如果可偷的商品为0.5kg. 则x轴的粒度要为0.5。既0.5->1->1.5->2…
3.  选择商品的时候，每个商品都是独立选择的，不存在依赖关系。例如不应该出现选择商品A，则必须（不能）选择B的情况
4.  最优解可能会导致最终的背包没有被装满

# 3. 最长公共子串 #

最场公共子串求出的是两个字符串都包含的最长子串，例如:对于hish与fish两个单词，ish就是他们的最长公共子串。

## 3.1 思路 ##

可以用解决背包问题的思路来解决该问题，两个单词分别对应纵/横轴，将公共子串的长度填到方格里，最后所有格子里最大的值就是最大的公共子串的长度，连续从0到最大长度值对应的纵/横轴对应的字母就是最长公共子串。

格子里值的推算公式如下：

if word_a[i] == word_b[j]:
        cell[i][j] = cell[i-1][j-1] + 1
    else:
        cell[i][j] = 0

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]

按照上面的公式推算，FISH与HISH的结果如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 1]

既最大长度为3,对应的子串为ISH.

# 3.2 最长公共子序列 #

最长公共子序列：两个单词中都有的序列包含的字母数，最后求得的子序列长度越长，说明两个单词越相似

算法的步骤如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 2]

计算FOSH与FISH与FORT两个单词的最长公共子序列的过程与结果如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 3]

通过上述结果可看出，FISH与FOSH更像一些。

# 4. 总结 #

动态规划的实际应用包括如下场景：

*  生物学家根据最长公共序列来确定DNA链的相似性，进而判断度两种动物或疾病有多相似。
 *  前面讨论了字符串的相似程度。 编辑距离（ levenshtein distance）指出了两个字符串的相  
    似程度，也是使用动态规划计算得到的。编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否是盗版，都在其中。
 *  Microsoft Word等具有断字功能的应用程序，使用动态规划确定在什么地方断  
    字以确保行长一致。

[20191113171125313.jpg]: https://img-blog.csdnimg.cn/20191113171125313.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191113171153457.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191113171235431.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191113171254429.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191113171311199.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY=,size_16,color_FFFFFF,t_70