0-1背包问题及Python代码实现
原⽂：
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新手代码及作用
4、代码实现import numpy as np def solve(vlist,wlist,totalWeight,totalLength):    resArr = np.zeros((totalLength+1,totalWeight+1),dtype=np.int32)    for i in range(1,totalLength+1):        for j in range(1,totalWeight+1):            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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
5、复杂度优化
以上⽅法的时间和空间复杂度均为 O(N*W)，其中时间复杂度基本已经不能再优 化了，但空间复杂度却可以优化到 O(W)。
先考虑上⾯讲的基本思路如何实现，肯定是有⼀个主循环 i=1…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]]的值呢? 事实上，这要求在每次主循环中我们以 v=V…0 的顺序推 f[w]，这样才能保证推 f[v]时 f[v-w[i]]保存的是状态 f[i-1][w-w[i]]的值。改进后的代码如下：6、进⼀步思考
我们看到的求最优解的背包问题题⽬中，事实上有两种不太相同的问法。有的题 ⽬要求“恰好装满背包”时的最优解，有的题⽬则并没有要求必须把背包装满。 ⼀种区别这两种问法的实现⽅法是在初始化的时候有所不同。
如果是第⼀种问法，要求恰好装满背包，那么在初始化时除了 f[0]为 0 其它 f[1…W]均设为-∞，这样就可以保证最终得到的 f[N]是⼀种恰好装满背包的最 优解。
如果并没有要求必须把背包装满，⽽是只希望价格尽量⼤，初始化时应该将 f[0…W]全部设为 0。
为什么呢?可以这样理解：初始化的 f 数组事实上就是在没有任何物品可以放⼊ 背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可能 被价值为 0 的 nothing“恰好装满”，其它容量的背包均没有合法的解，属于未 定义的状态，它们的值就都应该是-∞了。如果背包并⾮必须被装满，那么任何 容量的背包都有⼀个合法解“什么都不装”，这个解的价值为 0，所以初始时状 态的值也就全部为 0 了。
这个⼩技巧完全可以推⼴到其它类型的背包问题，后⾯也就不再对进⾏状态转移 之前的初始化进⾏讲解。
7、总结
01 背包问题是最基本的背包问题，它包含了背包问题中设计状态、⽅程的最基 本思想，另外，别的类型的背包问题往往也可以转换成 01背包问题求解。故⼀ 定要仔细体会上⾯基本思路的得出⽅法，状态转移⽅程的意义，以及最后怎样优 化的空间复杂度def solve2(vlist,wlist,totalWeight,totalLength):    resArr = np.zeros((totalWeight)+1,dtype=np.int32)    for i in range(1,totalLength+1):        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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。