本章内容

学习动态规划，这是一种解决棘手问题的方法，它将问题分成小问题，并先着手解决这 些小问题。
学习如何设计问题的动态规划解决方案。

本章小结

需要在给定约束条件下优化某种指标时，动态规划很有用。
问题可分解为独立的离散子问题时，可使用动态规划来解决。
每种动态规划解决方案都涉及网格。
单元格中的值通常就是你要优化的值。
每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
没有放之四海皆准的计算动态规划解决方案的公式。

练习

image.png
解答：C+M+W=25

1 2 3 4 5 6
水W(3-10) W=10 W=10 W=10 W=10
书B(1-3) B=3 B=3 W=10 W=10 W+B=13 W+B=13
食物M(2-9) B=3 M=9 M+B=12 M+B=12 M+W=19 M+W+B=22
夹克J(2-5) B=3 M=9 M+B=12 J+M=14 M+W=19 M+W+B=22
相机C(1-6) C=6 M=9/C+B=9 C+M=15 C+M+B=18 M+W=19 C+M+W=25

9.1 背包问题

image.png

9.1.1 简单算法

最简单的算法如下：尝试各种可能的商品组合，并找出价值最高的组合。

  • 这种算法的运行时间 为O(2 )。

9.1.2 动态规划

动规的原理：动态规划先解决子问题，再逐步解决大问题。
image.png

每个动态规划算法都从一个网格开始，背包问题的网格如下。我们需要做的是沿着自上向下的列的方向，逐行地一步步迭代填满这个网格，在最新的一行中，各列的填充便是对应大小的背包的最优解。
image.png

  • 备注：各个小书包的容量是由吉他、笔记本、音响的重量决定的。

对于各个背包，我们依靠以下公式来决定怎样填充的单元格（当然，前提是商品重量已满足装入的条件）：
image.png

  • 细节：剩余空间的价值 = cell[i-1][j-当前商品的重量] 。可见，各个背包的大小是由商品重量决定的。

逐行迭代：

  1. 吉他G（1磅，1500美金）行：
    1. 1~4磅背包均可装入G，且依据公式决定都装入，且2~4磅背包有剩余空间，但是目前仅可偷G。image.png

  1. 音响S（4磅，3000美金）行：

    1. 仅可装入4磅背包，且依据公式决定装入，并且无剩余空间。image.png

  2. 电脑L（3磅，2000美金）行：

    1. 可装入3磅背包，且依据公式决定装入L，并且无剩余空间。image.png
    2. 可装入4磅背包，且依据公式决定装入L，并且有剩余空间1磅，将剩余空间装入G。image.png

答案如下：将吉他和笔记本电脑装入背包时价值最高，为3500美元。


9.2 背包问题 FAQ

9.2.1 再增加一件商品将如何呢

假设你发现还有第四件商品可偷——一个手机I（1磅）2000美金！

增加逐行迭代：

手机I（1磅，2000美金）行：1~4磅背包均可装入，依据公式均决定装入，并且有不同情况的剩余空间，再将各个书包的剩余空间装入。
image.png

问题：沿着一列往下走时，最大价值有可能降低吗？
答案：不可能。每次迭代时，你都存储当前的最大价值。最大价值不可能比以前低

练习：假设你还可偷另外一件商品——MP3播放器，它重1磅，价值1000美元。你要偷吗？
答案：不偷，虽然可装入1~4个背包中，但是依据公式不应该装入。


9.2.3 可以逐列而不是逐行填充网格吗

就这个问题而言，这没有任何影响，但对于其他问题，可能有影响。

9.2.4 增加一件更小的商品将如何呢

现在还可以偷一条项链，它重0.5磅，价值1000美元。

再次增加逐行迭代

由于项链的加入，你需要考虑的粒度更细，因此必须调整网格。
image.png

9.2.5 可以偷商品的一部分吗

假设你在杂货店行窃，可偷成袋的扁豆和大米，但如果整袋装不下，可打开包装，再将背包倒满。在这种情况下，不再是要么偷要么不偷，而是可偷商品的一部分。如何使用动态规划来处理这种情形呢？

  • 答案是动态规划没法处理。使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而没法判断该 不该拿走商品的一部分。
  • 但使用贪婪算法可轻松地处理这种情况！首先，尽可能多地拿价值最高的商品；如果拿光了， 再尽可能多地拿价值次高的商品，以此类推。

9.2.6 旅游行程最优化

image.png

建立动态规划的网格：
image.png

逐行迭代：
image.png

9.2.7 处理相互依赖的情况

  1. ![image.png](https://cdn.nlark.com/yuque/0/2020/png/956564/1583274036331-27eb73cd-6787-4314-90ff-38ffff8b4f97.png#align=left&display=inline&height=144&name=image.png&originHeight=227&originWidth=810&size=55694&status=done&style=none&width=513)

如上这个清单：由于这个三个地点都在巴黎，所以一旦将其中任意一个地点加入“背包”后，其余的地点都更“便宜”：只要1天时间，而不是1.5天。如何使用动态规划对这种情况建模呢？

  • 没办法建模。动态规划功能强大，它能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。这意味着使用动态规划算法解决不了去巴黎玩的问题

9.2.8 计算最终的解时会涉及两个以上的子背包吗

为获得前述背包问题的最优解，可能需要偷两件以上的商品。但根据动态规划算法的设计，最多只需合并两个子背包，即根本不会涉及两个以上的子背包。不过这些子背包可能又包含子背包。image.png

9.2.9 最优解可能导致背包没装满吗

当然可能没装满。因为最优解是价值最高，不代表会装满。

9.3 最长公共子串

动态规划启示：

  • 动态规划可帮助你在给定约束条件下找到最优解。（背包问题中的给定背包容量）
  • 在问题可分解为彼此独立且离散的子问题时，才可以用动规。
  • 每种动态规划解决方案都涉及网格。
  • 单元格中的值通常就是你要优化的值。（在背包问题中，单元格的值为商品的价值。）
  • 每个单元格都是一个子问题。因此你应考虑如何将问题分成子问题，这有助于你找出网格的坐标轴。

9.3.1 绘制网格

思考的点：单元格中的值是什么？ 如何将这个问题划分为子问题？ 网格的坐标轴是什么？

案例1

查找 hish 和 fish 的最长子串。
image.png

案例2

查找单词hish和vista的最长公共子串
image.png

  • 对于最长公共子串问题，答案为网格中最大的数字——它可 能并不位于最后的单元格中。

伪代码：

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

9.3.4 最长公共子序列

不小心输入了fosh，他原本想输入的是fish还是fort呢？

  1. image.png
  • 两者的的最长公共子串是一样长的，所以，其实我们需要的是最长公共子序列。

9.3.5 最长公共子序列之解决方案

image.png

  • 填充公式如下：
    1. 如果两个字母不同，就选择上方和左方邻居中较大的那个（不同于计算最长公共子串）
    2. 如果两个字母相同，就将当前单元格的值设置为“左上方的值+1”（相同于计算最长公共子串）

伪代码：

if word_a[i] == word_b[j]:
     cell[i][j] = cell[i-1][j-1] + 1
else:
     cell[i][j] = max(cell[i-1][j], cell[i][j-1])