看的懂的动态规划解释(动态规划求解0/1背包问题)
网上看到的中文对动态规划的解说以及样例让我很火大。不说清楚总体思路就跳到细节里。给的代码也是用尽没有说明的单字母缩写。不明所以的循环。 而维基你懂得。你要看懂一篇，先得把里面专业名词，各种数学全了解遍。
以0/1背包问题为例。先说明问题。【我就不用背景故事了。钻石还是砖头都无所谓】 有N个物品。每个物品有两个属性。它所占的空间或着说重量weight.和它的价值value。 和一个容器[背包]，背包有最大容量Capacity。求此背包能放下的东西的最大价值。
先看下暴力搜索是怎么处理的，把能放进去的物品的每种放法全部穷举一遍。找出最大值。 而贪心则是先放性价比最高的[value/weight最大]。再放其次。依次类推。
动态规划，带着如此高端大气上档次的名字。其实很简单，是做出一张表，得到最大值。 表如下：
物品1 只有物品1能达到的最大值
物品2 只有物品1和物品2能达到的最大值
物品3 有物品1和物品2和物品3能达到的最大值
物品4 有物品1、2、3、4能达到的最大值
...
物品n
背包容量为1 2 3 4 ... Capacity
动态规划先把只有物品1在不同容量下能达到的最大价值列举出来。 看具体例子，有以下四个物品。3h什么的是weight[或者说cost]。100€是价值(value)。
A 3h 100€
B 5h 120€
C 4h 80€
D 1h 50€
那么在计算第一行，只有A物品的情况后得到的表是这样子的：
A 0 0 100 100 100 100 100 100
B 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 0
D 0 0 0 0 0 0 0 0
容量 1 2 3 4 5 6 7 8
当然，程序里是没有第一列的ABCD和底下一行的容量的。那是我为了标注清楚加上去的。
第一行。只有物品A。在容量为1和2时，放不下，故最大价值为0。容量3到8只能放A。最大价值为100。
A 0 0 100 100 100 100 100 100
B 0 0 100 100 120 120 120 220
C 0 0 0 0 0 0 0 0
D 0 0 0 0 0 0 0 0
容量 1 2 3 4 5 6 7 8
注意，这里是动态规划的精华部分。
现在计算第二行。此时新加入物品B 5h 120€。
[注意动态规划并不关心之前是几个物品，怎么放的。只要知道上一行(在没加此行新物品时)在不同容量下的最大价值即可。]。
当容量是1到4时，是不可能放下物品B的。故跟没有物品B的最大价值一致。也就是跟上面一格值相同。 当容量是5时，有几种选择。
1.不放B，价值为上面一格，也就是100.
2.放B，价值为: B的价值120 加上 在没有B、容量为0情况下的最大价值[也就是上一行第0列]，也就是0。得到120.
当前容量5减掉B的重量(weight)5 得到的0。 选择两种情况种大的，便是容量为5,新加B情况下的最大价值。
我们再来看第二行最后一个220是如何得到的。[显然它是同时放了A和B，但重点是我们要理解动态规划是如何得到这个值的]
此时计算的是容量为8,新加物品B 5h 120€。
1.不放B，价值为上面一格，也就是100.
2.放B，价值为: B的价值120 加上 在没有B、容量为3情况下的最大价值[也就是上一行第3列]，也就是100。得到220.
当前容量8减掉B的重量(weight)5 得到的3。 为什么要加上没有B。容量为(当前容量减B重量)的值？因为这样子就可以得到把B放进去得到的最大值了。
重复这一过程就能把整个表完成。而右下那个格子就是我们要求的情况。有n个物品。容量为Capacity所能达到的最大价值。 贴一下中间过程。可以看着思索下。脑中模拟下。
0 0 0 0 0 0 0 0 0
0 0 0 100 100 100 100 100 100
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 100 100 100 100 100 100
0 0 0 100 100 120 120 120 220
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 100 100 100 100 100 100
0 0 0 100 100 120 120 120 220
0 0 0 100 100 120 120 180 220
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 100 100 100 100 100 100
0 0 0 100 100 120 120 120 220
0 0 0 100 100 120 120 180 220
0 50 50 100 150 150 170 180 230
Cars chosen to repair:
D 1h 50€
C 4h 80€
A 3h 100€
Total revenue:
230
多出来的第一行0和第一列0是为了让下标符合题目的语义。容量1就是下标1.物品1就是下标1。
关于代码见https://github.com/c19/java_exercise/tree/master/car_repair
相信看懂后不看代码也能顺利写出动态规划。
误解与选法倒推
请务必牢记价值表的含义。
动态规划在计算每个格子的时候，考虑的都只是那个格子的情况。这个格子的情况会不会被最终解引用。这个元素在最终解中到底会不会被加入。动态规划是不知道的。也不关心。
动态规划的出表后所得到的只是能获得的最大价值。并不是选择方式。然而选择方式可以通过价值表倒推得到。
0 0 0 0 0 0 0 0 0
0 0 0 100 100 100 100 100 100
0 0 0 100 100 120 120 120 220
0 0 0 100 100 120 120 180 220
0 50 50 100 150 150 170 180 230
先查看右下角格子。跟它上方的格子比较，如果比上方的大。意味着：背包容量为8.有D物品比没有D物品的最大价值要大。也就是背包容量为8,有D物品的情况下，D物品被放入了。
然后我们把D物品(D 1h 50€)的空间/重量减掉。剩余容量7。不包含D物品。查看C行，第7列。是180,大于它上方的120.同理说明C也被选中了。
把C 4h 80€的重量减掉，剩余容量3.查看B行，第3列。是100。和它上方的100(A,3)相同。故B没有被选入。
这时查看(A,3)100上方的格子，(因为B未选中，我们就可以移动到不包含B的情况了。)。是0.小于100.故A被选中了。
Written with StackEdit.