1、简介假设我们有n件物品分别编号为1, 2...n。其中编号为i的物品价值为vi它的重量为wi。为了简化问题假定价值和重量都是整数值。现在假设我们有一个背包它能够承载的重量是W。现在我们希望往包里装这些物品使得包里装的物品价值最大化那么我们该如何来选择装的东西呢问题结构如下图所示这个问题其实根据不同的情况可以归结为不同的解决方法。假定我们这里选取的物品每个都是独立的不能选取部分。也就是说我们要么选取某个物品要么不能选取不能只选取一个物品的一部分。这种情况我们称之为0-1背包问题。而如果我们可以使用部分的物品的话这个问题则成为部分背包(fractional knapsack)问题。这里我们只考虑0-1背包问题。2、初步分析对于这个问题一开始确实有点不太好入手。一堆的物品每一个都有一定的质量和价值我们能够装入的总重量有限制该怎么来装使得价值最大呢对于这n个物品每个物品我们可能会选也可能不选那么我们总共就可能有2^n种组合选择方式。如果我们采用这种办法来硬算的话则整体的时间复杂度就达到指数级别的肯定不可行。现在我们换一种思路。既然每一种物品都有价格和重量我们优先挑选那些单位价格最高的是否可行呢比如在下图中我们有3种物品他们的重量和价格分别是10, 20, 30 kg和60, 100, 120。那么按照单位价格来算的话我们最先应该挑选的是价格为60的元素选择它之后背包还剩下50 - 10 40kg。再继续前面的选择我们应该挑选价格为100的元素这样背包里的总价值为60 100 160。所占用的重量为30, 剩下20kg。因为后面需要挑选的物品为30kg已经超出背包的容量了。我们按照这种思路能选择到的最多就是前面两个物品。如下图按照我们前面的期望这样选择得到的价值应该是最大的。可是由于有一个背包重量的限制这里只用了30kg还有剩下20kg浪费了。这会是最优的选择吗我们看看所有的选择情况很遗憾在这几种选择情况中我们前面的选择反而是带来价值最低的。而选择重量分别为20kg和30kg的物品带来了最大的价值。看来我们刚才这种选择最佳单位价格的方式也行不通。3、动态规划思路既然前面两种办法都不可行我们再来看看有没有别的方法。我们再来看这个问题。我们需要选择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]一样。这里有一点值得注意这里的wi指的是第i个物品的重量而不是到第i个物品时的总重量。另外对于初始的情况呢很明显c[0, w]里不管w是多少肯定为0。因为它表示我们一个物品都不选择的情况。c[i, 0]也一样当我们总重量限制为0时肯定价值为0。这样基于我们前面讨论的这3个部分我们可以得到一个如下的递推公式有了这个关系我们可以更进一步的来考虑代码实现了。我们有这么一个递归的关系其中后面的函数结果其实是依赖于前面的结果的。我们只要按照前面求出来最基础的最优条件然后往后面一步步递推就可以找到结果了。我们再来考虑一下具体实现的细节。这一组物品分别有价值和重量我们可以定义两个数组int[] v, int[] w。v[i]表示第i个物品的价值w[i]表示第i个物品的重量。为了表示c[i, w]我们可以使用一个int[i][w]的矩阵。其中i的最大值为物品的数量而w表示最大的重量限制。按照前面的递推关系c[i][0]和c[0][w]都是0。而我们所要求的最终结果是c[n][w]。所以我们实际中创建的矩阵是(n 1) x (w 1)的规格。Python代码实现import numpy as np def solve(vlist,wlist,totalWeight,totalLength): resArr np.zeros((totalLength1,totalWeight1),dtypenp.int32) for i in range(1,totalLength1): for j in range(1,totalWeight1): if wlist[i] j: resArr[i,j] max(resArr[i-1,j-wlist[i]]vlist[i],resArr[i-1,j]) else: resArr[i,j] resArr[i-1,j] return resArr[-1,-1] if __name__ __main__: v [0,60,100,120] w [0,10,20,30] weight 50 n 3 result solve(v,w,weight,n) print(result)5、复杂度优化以上方法的时间和空间复杂度均为 O(N*W)其中时间复杂度基本已经不能再优 化了但空间复杂度却可以优化到 O(W)。先考虑上面讲的基本思路如何实现肯定是有一个主循环 i1..N每次算出来 二维数组 f[i][0..W]的所有值。那么如果只用一个数组 f[0..W]能不能保证 第 i 次循环结束后 f[w]中表示的就是我们定义的状态 f[i][w]呢?f[i][w]是由 f[i-1][w]和 f[i-1][w-c[i]]两个子问题递推而来能否保证在推 f[i][w]时(也 即在第 i 次主循环中推 f[w]时)能够得到 f[i-1][w]和 f[i-1][w-w[i]]的值呢? 事实上这要求在每次主循环中我们以 vV..0 的顺序推 f[w]这样才能保证推 f[v]时 f[v-w[i]]保存的是状态 f[i-1][w-w[i]]的值。改进后的代码如下def solve2(vlist,wlist,totalWeight,totalLength): resArr np.zeros((totalWeight)1,dtypenp.int32) for i in range(1,totalLength1): for j in range(totalWeight,0,-1): if wlist[i] j: resArr[j] max(resArr[j],resArr[j-wlist[i]]vlist[i]) return resArr[-1] if __name__ __main__: v [0,60,100,120] w [0,10,20,30] weight 50 n 3 result solve2(v,w,weight,n) print(result)6、进一步思考我们看到的求最优解的背包问题题目中事实上有两种不太相同的问法。有的题 目要求“恰好装满背包”时的最优解有的题目则并没有要求必须把背包装满。 一种区别这两种问法的实现方法是在初始化的时候有所不同。如果是第一种问法要求恰好装满背包那么在初始化时除了 f[0]为 0 其它 f[1..W]均设为-∞这样就可以保证最终得到的 f[N]是一种恰好装满背包的最 优解。如果并没有要求必须把背包装满而是只希望价格尽量大初始化时应该将 f[0..W]全部设为 0。为什么呢?可以这样理解:初始化的 f 数组事实上就是在没有任何物品可以放入 背包时的合法状态。如果要求背包恰好装满那么此时只有容量为 0 的背包可能 被价值为 0 的 nothing“恰好装满”其它容量的背包均没有合法的解属于未 定义的状态它们的值就都应该是-∞了。如果背包并非必须被装满那么任何 容量的背包都有一个合法解“什么都不装”这个解的价值为 0所以初始时状 态的值也就全部为 0 了。这个小技巧完全可以推广到其它类型的背包问题后面也就不再对进行状态转移 之前的初始化进行讲解。7、总结01 背包问题是最基本的背包问题它包含了背包问题中设计状态、方程的最基 本思想另外别的类型的背包问题往往也可以转换成 01 背包问题求解。故一 定要仔细体会上面基本思路的得出方法状态转移方程的意义以及最后怎样优 化的空间复杂度
