谈论动态规划,就需要提及另一个算法:贪心算法。
某些现实中的问题可以采取贪心思路来解决:局部最优,最终达到全局最优。计算出结果。
然而不幸的是,不是所有的问题都有局部最优就能得到全局最优的特性。解决思路比NP完全问题的处理稍微好受一点。通过将问题拆分成子问题,逐个解决。它有局部最优的特性,但是相比贪心算法考虑的更多,下面就说说这类解决方案:动态规划。
在动态规划的领域,比较经典的问题就是01背包。它的场景是这样的:游戏主人公有一个容量有限的背包,他有一些可供选择的物品。每一件物品都有自己的价值与所占空间。问,背包可以装下物品的最大价值是多少?
假设背包的容量是V。
那么我们通常需要考虑V – x 和 x的背包情况,比较两者之和 与 容量为V的结果。
每一个物体有两种使用情况:装到背包里,不装到背包里。
所以,思考的维度是2。我们得到了一张表格。

1(Volumn) 2 3 4 5
value1
value2

表格的列表示容量,行表示物品(决定需要还是不需要)。
例子 杭州电子科技大学在线测试问题:
http://acm.hdu.edu.cn/showproblem.php?pid=2602

5 10
1 2 3 4 5
5 4 3 2 1

有5个物体,背包的容量是10,第2行是物品的价值,第3行是物品的体积。
按照之前提过的思路,我们可以得到下面的表格:

1 2 3 4 5 6 7 8 9 10
0 0 0 0 1 1 1 1 1 1
0 0 0 2 2 2 2 2 3 3
0 0 3 3 3 3 5 5 5 5
0 4 4 4 7 7 7 7 9 9
5 5 9 9 9 12 12 12 12 14

在更新的过程中,我们用到了这样的公式:
f[i][v] = max(f[i-1][v], value[i] + f[i-1][v-volumn[i]])
有可能自己没有意识到,但是新的一行的确是由下一行推导出来的。
由此,转化成代码,得到:

import numpy as np
dp = np.zeros((6, 11), dtype=np.int)

value = [-1, 1, 2, 3, 4, 5]
volumn = [-1, 5, 4, 3, 2, 1]

for i in range(1, 6):
    for v in range(1, 11):
        if( volumn[i] <= v ):
            if( 1 == i ):
                dp[i][v] = value[i])
            else:
                dp[i][v] = max( dp[i-1][v], value[i] + dp[i-1][v-volumn[i]] )

print( dp )

[[ 0 0 0 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 1 1 1 1 1 1]
[ 0 0 0 0 2 2 2 2 2 3 3]
[ 0 0 0 3 3 3 3 5 5 5 5]
[ 0 0 4 4 4 7 7 7 7 9 9]
[ 0 5 5 9 9 9 12 12 12 12 14]]
[Finished in 0.2s]

上面的python代码为了方便使用从1开始的索引,设置value和volumn的第一个元素为-1. 我们不会使用它。
在仔细观察后,可以将循环中的if处理归纳成一条语句:

import numpy as np
dp = np.zeros((6, 11), dtype=np.int)

value = [-1, 1, 2, 3, 4, 5]
volumn = [-1, 5, 4, 3, 2, 1]

for i in range(1, 6):
    for v in range(1, 11):
        if( volumn[i] <= v ):
                dp[i][v] = max( dp[i-1][v], value[i] + dp[i-1][v-volumn[i]] )

print( dp )

 

Categories: AlgorithmPython

Leave a Reply

Your email address will not be published. Required fields are marked *