Dynamic programming（DP算法）
首先我们要知道为什么要使用(Dynamic programming)dp，我们在选择dp算法的时候，往往是在决策问题上，而且是在如果不使用dp，直接暴力效率会很低的情况下选择使用dp。
那么问题来了，什么时候会选择使用dp呢，一般情况下，我们能将问题抽象出来，并且问题满足无后效性，满足最优子结构，并且能明确的找出状态转移方程的话，dp无疑是很好的选择。
无后效性通俗的说就是只要我们得出了当前状态，而不用管这个状态怎么来的，也就是说之前的状态已经用不着了，如果我们抽象出的状态有后效性，很简单，我们只用把这个值加入到状态的表示中。
最优子结构(自下而上)：在决策问题中，如果，当前问题可以拆分为多个子问题，并且依赖于这些子问题，那么我们称为此问题符合子结构，而若当前状态可以由某个阶段的某个或某些状态直接得到，那么就符合最优子结构。
重叠子问题(自上而下)：动态规划算法总是充分利用重叠子问题，通过每个子问题只解一次，把解保存在一个需要时就可以查看的表中，每次查表的时间为常数，如备忘录的递归方法。斐波那契数列的递归就是个很好的例子。
状态转移：这个概念比较简单，在抽象出上述两点的的状态表示后，每种状态之间转移时值或者参数的变化。
背包问题
如何选择使价值最大化
我们来看这个问题。我们需要选择n个元素中的若干个来形成最优解，假定为k个。那么对于这k个元素a1, a2, ...ak来说，它们组成的物品组合必然满足总重量<=背包重量限制，而且它们的价值必然是最大的。因为它们是我们假定的最优选择嘛，肯定价值应该是最大的。假定ak是我们按照前面顺序放入的最后一个物品。它的重量为wk，它的价值为vk。既然我们前面选择的这k个元素构成了最优选择，如果我们把这个ak物品拿走，对应于k-1个物品来说，它们所涵盖的重量范围为0-(W-wk)。假定W为背包允许承重的量。假定最终的价值是V，剩下的物品所构成的价值为V-vk。这剩下的k-1个元素是不是构成了一个这种W-wk的最优解呢？
我们可以用反证法来推导。假定拿走ak这个物品后，剩下的这些物品没有构成W-wk重量范围的最佳价值选择。那么我们肯定有另外k-1个元素，他们在W-wk重量范围内构成的价值更大。如果这样的话，我们用这k-1个物品再加上第k个，他们构成的最终W重量范围内的价值就是最优的。这岂不是和我们前面假设的k个元素构成最佳矛盾了吗？所以我们可以肯定，在这k个元素里拿掉最后那个元素，前面剩下的元素依然构成一个最佳解。
现在我们经过前面的推理已经得到了一个基本的递推关系，就是一个最优解的子解集也是最优的。可是，我们该怎么来求得这个最优解呢？我们这样来看。假定我们定义一个函数c[i, w]表示到第i个元素为止，在限制总重量为w的情况下我们所能选择到的最优解。那么这个最优解要么包含有i这个物品，要么不包含，肯定是这两种情况中的一种。如果我们选择了第i个物品，那么实际上这个最优解是c[i - 1, w-wi] + vi。而如果我们没有选择第i个物品，这个最优解是c[i-1, w]。这样，实际上对于到底要不要取第i个物品，我们只要比较这两种情况，哪个的结果值更大不就是最优的么？
在前面讨论的关系里，还有一个情况我们需要考虑的就是，我们这个最优解是基于选择物品i时总重量还是在w范围内的，如果超出了呢？我们肯定不能选择它，这就和c[i-1, w]一样。
另外，对于初始的情况呢？很明显c[0, w]里不管w是多少，肯定为0。因为它表示我们一个物品都不选择的情况。c[i, 0]也一样，当我们总重量限制为0时，肯定价值为0。
这样，基于我们前面讨论的这3个部分，我们可以得到一个如下的递推公式：
推导公式
有了这个关系，我们可以更进一步的来考虑代码实现了。我们有这么一个递归的关系，其中，后面的函数结果其实是依赖于前面的结果的。我们只要按照前面求出来最基础的最优条件，然后往后面一步步递推，就可以找到结果了。
# n个物体的重量(w[0]无用)
w = [0, 2, 2, 6, 5, 4]
# n个物体的价值(p[0]无用)
p = [0, 6, 3, 5, 4, 6]
# 计算n的个数
n = len(w) - 1
# 背包的载重量
m = 10
# 装入背包的物体，元素为True时，对应物体被装入(x[0]无用)
x = [False for raw in range(n + 1)]
v = 0
# optp[i][j]表示在前i个物体中，能够装入载重量为j的背包中的物体的最大价值
optp = [[0 for col in range(m + 1)] for raw in range(n + 1)]
def knapsack_dynamic(w, p, n, m, x):
# 计算optp[i][j]
for i in range(1, n + 1):
for j in range(1, m + 1):
optp[i][j] = optp[i - 1][j]
if (j >= w[i]) and (optp[i - 1][j - w[i]] + p[i] > optp[i - 1][j]):
optp[i][j] = optp[i - 1][j - w[i]] + p[i]
# 递推装入背包的物体
j = m
for i in range(n, 0, -1):
if optp[i][j] > optp[i - 1][j]:
x[i] = True
j = j - w[i]
v = optp[n][m]
return v
print('最大价值为：' + str(knapsack_dynamic(w, p, n, m, x)))
print(x[1:])
结果
此题的核心就在d_k两个循环体里，因为之前已经实现了一个类二维数组，所有dp[ 0 ] [ j ] dp[ i ][ 0 ]都是零，所以从i=1开始，通过循环--递归一层一层的赋值，所有的下一层值都由上一层的值相等决定或者，dp i-1，j-w[ i ]+p[ i ]决定，最后全部铺满，在求最大值的时候，直接取表格中的值即可。
网友评论