动态路径规划算法有哪些,几个经典的动态规划算法

图6-5

第3步，再加入4磅的电脑。在第2行中的各单元格的总价值的计算公式如下：

S(2,j)=max {v[2] S(1,c[j]-w[2]),S(1,j)}

S(2, j)---表示第2行，第j列的单元格的总价值；

v[2] --- 表示第2行的商品(即电脑)的价值；

w[2] --- 表示第2行的商品(即电脑)的重量；

c[j] --- 表示第j列的小背包的容量，一般c[j]=j；(例如，第1列背包的容量是1磅， 第2列的背包的容量是2磅， 第3列的背包的容量是3磅，...， 第6列的背包的容量是6磅)

c[j]-w[2] --- 表示加入电脑后，第j列的背包的容量减去电脑重量后的剩余容量，刚好对应着以前的列号。

S(1, j) --- 表示第1行第j列的单元格的总价值。

对计算公式第一种理解方法：

加入当前商品（电脑）后，当前行中的各单元格的总价值等于①与②的最大值。

①　当前加入的商品（电脑）的价值 上一行中剩余背包容量（当前行的各单元格对应的背包容量减去当前加入的商品的重量）所在的列对应的单元格的总价值；

②　同一列(即同一背包的容量)的上一行单元格(即上一次计算)的已经加入的商品的总价值。

对计算公式第二种理解方法：

如图中红色标记部分， 第2行第6列的计算总价值 = max { 第1行第2列的单元格的总价值$1500 当前电脑的价值$2000, 第1行第6列的单元格的总价值$1500 }， 即两者取最大值。 为什么是第1行第2列呢？因为第6列的容量是6磅，减去加入的电脑的重量4磅，剩余的容量为2磅，对应的就是第2列。

图6-6

第4步，再加入5磅的音响。在第3行中的各单元格的总价值的计算公式如下：

S(3, j) = max {v[3] S(2,c[j]-w[3]),S(2, j)}

S(3, j)---表示第3行，第j列的单元格的总价值；

v[3] --- 表示第3行的商品(即音响)的价值；

w[3] --- 表示第3行的商品(即音响)的重量；

c[j] --- 表示第j列的小背包的容量，一般c[j]=j；(例如，第1列背包的容量是1磅，第2列的背包的容量是2磅， 第3列的背包的容量是3磅，...，第6列的背包的容量是6磅）

c[j]-w[3] --- 表示加入音响后，第j列的背包的容量减去音响重量后的剩余容量，刚好对应着以前的列号。

S(2, j) --- 表示第2行第j列的单元格的总价值。

对计算公式第一种理解方法：

加入当前商品（音响）后，当前行中的各单元格的总价值等于①与②的最大值。

③　当前加入的商品（音响）的价值 上一行中剩余背包容量（当前行的各单元格对应的背包容量减去当前加入的商品的重量）所在的列对应的单元格的总价值；

④　同一列(即同一背包的容量)的上一行单元格(即上一次计算)的已经加入的商品的总价值。

对计算公式第二种理解方法：

如图中红色标记部分， 第3行第6列的计算总价值 = max { 第2行第1列的单元格的总价值0 当前音响的价值 $3000, 第2行第6列的单元格的总价值$3500 }， 即两者取最大值。 为什么是第2行第1列呢？因为第6列的容量是6磅，减去加入的音响的重量5磅，剩余的容量为1磅，对应的就是第1列。

图6-7

经过第4步加入手机、第5步加入MP3后，计算得到满的网格数据，红色标记的最后一行就是对应的各容量能够获取的商品的最大总价值。例如：1磅的容量能获取$1200, 2磅的容量能获取$1700, 3磅的容量能获取$2700, 4磅的容量能获取$3200, 5磅的容量能获取$3200, 6磅的容量能获取$4200。

图6-8

小结：

问题1：再新加一件商品，沿着往下走时，最大价值有可能降低吗？

答案：不可能。每次迭代时，你都存储当前的最大价值。最大价值不可能比以前低。

问题2：行的排列顺序发生变化时结果将如何？答案会随之变化吗？

假设你按如下顺序填充各行：手机、音响、电脑、MP3、吉他。网格将会是什么样的？

答案：没有变化。也就是说，各行的排列顺序无关紧要。

问题3：可以逐列而不是逐行填充网格吗？

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

动态规划先解决子问题，再逐步解决大问题。 对于背包问题，你先解决小背包（子背包）问题，再逐步解决原来的问题。

0-1背包问题用二维矩阵的网格解决，矩阵的行表示n个物品，列表示背包逐步增长的容量, 是从1增长到c，也就是从小背包容量增长到待求背包容量。

其状态转移函数：S(i, j) = max { v[i] S(i-1, j- w[i]), S(i-1, j)} 1≤i≤n, 1≤j≤c

S(i, j)---表示第i行，第j列的单元格的总价值；

v[i] --- 表示第i行的物品的价值；

w[i] --- 表示第i行的物品的重量；

j --- 既表示列号，又表示第j列的小背包的容量;

j-w[i] --- 表示加入物品后，第j列的小背包的容量减去该物品重量后的剩余容量，刚好对应着以前的列号。

S(i-1, j) --- 表示第i-1行第j列的单元格的总价值。

0-1背包问题的空间复杂度与时间复杂度均为O(n*c)，其中n为物品数，c为背包容量。

已知：假设你管理着字典网站。用户在该网站输入单词时，你需要给出其定义。 但如果用户拼错了，你必须猜测他原本要输入的是什么单词。例如，Alex想查单词fish，但不小心输入了hish。

求：Alex输入了hish，那他原本要输入的是fish还是vista呢？

解答：

如何将这个问题划分为子问题呢？你可能需要比较子串：不是比较hish和fish，而是先比较his和fis。每个单元格都将包含这两个子串的最长公共子串的长度。这也给你提供了线索，让坐标轴很可能是这两个单词。

第1步 建立网格，单元格全部初始化为0。如图6-9所示。