动态规划，是算法初学者怎么也绕不开的大山……它分外让人头疼，云山雾绕，不得要领。我感觉，它其实是一种新的思维方式，让人学会打破常规思路去看待问题（只是我个人作为小白的不成熟的小领悟）。
动态规划中，有个经典的背包问题，也被称为0-1背包问题。这个问题是假设我有一个包，什么都想往里装，但是包就这么大，我想尽量装多点值钱的东西进去，怎么办？
这个问题看似炒鸡简单且贴近生活，但是实质上暗藏玄机，所以就有很多种很多种解法。
一般来说，根据生活常识，应该选择先装最贵的，但是这里有个致命的问题：如果最贵那个它体积也很大，那最后综合结果可能还不如装单价不那么贵但可以多塞几个的。
那然后我们就可以说，不然选取标准换成单位价值（直白点说就是性价比），意思就是：每个货物的价值除以它的体积，这样就可以避免只看那些虽然单价挺值钱但是大的要死的物品，但是问题并没有得到解决，因为背包的容量是一定的，无论如何在放每个物品前都要考虑的是：放了这个还能不能放别的，万一这个一个就把包装满了而放别的性价比低可以多塞几个更划算咋办？
那怎么解决到底拿哪些物品可以达到最优解呢？
正常人的思路都是从暴力求解法开始的，毕竟计算机就擅长这个，只要规则清晰明了，计算过程再复杂都不怕。其实每个物品都有两种选择：拿它，不拿，这也就是0-1背包问题的由来，拿了就是1，不拿就是0。那，大不了就把所有的组合都列一遍出来呗，只要最后选择拿的物品体积之和不大于包的容量就算一个可能的组合方式，再在这些可能解里找一个最大的值，看起来没啥问题。
有问题吗？有。最大的问题是，物品少些还成，物品稍微多一点，每加一个物品，循环就深一层，时间复杂度以指数形式坐火箭一样蹭蹭蹭往上窜。我们都知道，最坏最坏的算法，就是把时间复杂度搞成指数形式的，最好想都不要想，所以暴力求解法对背包问题来说只能是一个大大的NO。
硬攻搞不定，就只能学习智取了。
上面说到，0-1背包问题翻译一下是这样：有一长串儿的物品清单，每个都可以选择取或者不取，唯一的限制就是物品总量不能超过背包限制，并且物品是无法分割的。那么其实对每个物品取用状态都会对背包的剩余容积造成影响，这是一点。还有就是，假设我们是按照清单按顺序去查看每一个物品的，那么轮到每个物品的时候，我们都不太需要关注前面取了什么，只需要看背包剩余容量还能不能装，以及当前物品还要不要装这两件事。
为什么要这么想呢？这就涉及到动态规划一些基本的概念了。
首先要明确一点是，动态规划是个很方便的好登西，它可以把纷纷扰扰充满无数种可能的问题（比如指数级问题）转化为计算复杂度固定的问题，只不过需要牺牲一点儿空间来换取（毕竟世界很难两全其美）。它的思路呢，是化繁为简，把我们要解决的看似有无穷选择的复杂问题转化为子问题的递进解决。在我个人看来，动态规划和递归的思路有异曲同工之妙，只不过逼近真相的方向相反。递归代码上很简洁明了，但是不可避免地有大量重复计算，造成浪费，而动态规划可以利用起这些中间结果，一步步接近真相。
只可惜，如此化繁为简的良方，不是所有的问题都可以拿来如此这般抽丝剥茧抓住要害的。可以用动态规划来解决的问题都必须满足：最优解的子问题也需要是最优解。还有：前面做的选择不会影响到后面的选择。第一个条件还比较好理解，因为本来动态规划就是一步步推到最终结果的，假如前面的选择好坏都无所谓，那最后结果还怎么保证最优呢？第二个条件看起来稍有些迷惑——因为很显然，上一个东西装了可能会导致下一个装不进去，这难道不算是对后面的选择有影响吗？答案是：不算！因为每一个物品选择装或不装时，它们之间都是相互独立的，我不关心前面是不是选了A物品，我只关心前面所有物品占的体积，还有它们产生的最大价值，但是不会因为有了A物品就不可以选择B物品这样的限制，所以这就是无后效性。
我们回到背包问题本身，就刚刚的条件而言，它满足动态规划的基本前提，所以可以用动态规划来做。我们需要找到它的子问题，下面的话有些繁琐，但是对于理解这个问题来说是有一些用处的：对于每一个物品而言，都有装和不装的选项，假设此时问题中有5个物品，那么我们只看选到第5个物品时的情况（假设前面我们已经选到了用这个包装4个物品最值钱的取法）。现在第五个物品摆在眼前，首先想想是不是可装：这第五个物品本身有没有超过了背包的总容量？如果超过了只能直接放弃；下一步如果确定可以装，就要决定要不要装？判断准则也很明确：装的话需要保证这个取法更值钱（起码跟前四个物品最佳方案一样值钱，不然不如不装）。
仔细想想，第五个物品在背包容量足够装的情况下，判断值钱的装法，就是在选它所带来更新后的收益，和不选它的原来的收益里选一个最大值。不选它的收益，就跟用这个背包装四个物品的最优解是一样的，而选它的收益的计算方法是把背包里第五个物品将会占的空间去掉，剩下空间在只有四个物品时的最优解（假设我们也知道缩小的背包装四个物品最值钱的解法）加上第五个物品的价值。这两种收益选其中大值，就是我们要的，用背包装五个物品的最优解了。
上面这一大串啰里八嗦的话就是我对背包问题子问题的理解了，如果问题就是5个物体的选择，那么根据上面的思维过程，我们需要从算出1个物品装进背包最优解，推到2个，3个，4个才能一层层推出5个物体的最优解；同样，因为每加入一个新的物品都可能会用到剩余空间在没放这个物品情况下的最优解，所以选取组合容量也必须从1开始每一个值都计算，直到到背包真实容量为止。
这就是为什么背包问题的动态规划初始形态是填一张二维的表格，这个表格的纵轴是每个物品（应该理解为物品的累加：1-表示可选择的有物品1，2-表示可选择的有物品1，2……以此类推），横轴表示容量从1-递增到背包的容量上限。这张表格里的每一个格子表示：在当前的容量j下，可选的物品有1，2，…i 这些，此时的最优解。
实际的代码中，会多出一行表示当物体为0（意味着没有物品可放）的值，和一列背包容量为0（意味着背包什么也放不了）的值，它们在0-1背包问题中默认初始值都为0。前者是为初始化，这样放第一个物品的时候，如果背包装不下，就等同于没有物品可放；而后者是为了计算背包正好装满的时候，求剩余空间为0的最优解，可以正确返回0。
下面献上我很丑的代码：
#!/usr/bin/env python
# -*- coding:utf-8 -*-
def backpack_0_1(items,capacity,weights,values):
# 初始化表格
dp = [[0 for _ in range(capacity+1)] for _ in range(items+1)]
solution = []
for i in range(1,items+1):
for j in range(1,capacity+1):
if j <weights[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j],dp[i-1][j-weights[i-1]]+values[i-1])
# 返回物品选取方案
i = items
j = capacity
while i > 0:
print(i,j)
if dp[i][j] > dp[i-1][j]:
solution.append(i)
j -= weights[i-1]
i -= 1
return solution,dp[-1][-1]
print(backpack_0_1(4,10,[2,3,5,5],[2,4,3,7]))
网友评论