0-1 Knapsack Problem动态规划和递归方法python实现

0-1 Knapsack Problem

下面我们利用动态规划来解决一个实际问题叫做0-1背包问题。

如上有两个数组，一个是重量，一个是对应的价值。每个东西只能放一次，现在给出一个容量C的背包，问怎么装这些东西使得价值最大。

对于每一个东西，都有两种选择，放进背包还是不放，因此5个东西有$2^5$种方法。这个问题是个最大化问题，那么每一次决定都要使得value最大化。

首先我们用简单的递归来实现。

从后往前遍历，每个物体有放和不放的情况，如果是不放，那么直接跳到前一个物体，如果放，此时的value是当前放进的物体的value和剩余还没有放的value之后。

1.递归退出条件：东西装完了或者容量达到最大了 2.递归过程： 设函数为knp(n, C) 放进背包：v1 = v[n] + knp(n-1, C-w[i]) 不放：v2 = knp(n-1,C) vmax = max(v1, v2) 同时考虑一定不能放进背包的情况：重量大于容量 3.放回结果

代码如下，设c为10，计算得出的最大价值为16，与人工计算的结果相同。

w = [None, 1,2,4,2,5] v = [None,5,3,5,3,2] def knp(n, c): if n == 0 or c ==0 : result = 0 elif w[n] > c: result = knp(n-1, c) else: temp1 = v[n] + knp(n-1, c-w[n]) temp2 = knp(n-1, c) result = max(temp1, temp2) return result print(knp(5,10)) # output: 16

递归的方法尝试了所有的情况，其时间复杂度为$O(2^n)$，现在我们用动态规划的方法，修改上面的代码，同时用一个列表keep来标记哪个物体被放进背包里面。

import numpy as np w = [None, 1,2,4,2,5] v = [None,5,3,5,3,2] arr = np.zeros([6,11]) keep = [0]*6 def knp(n, c): if arr[n][c] != 0: return arr[n][c] if n == 0 or c ==0 : result = 0 elif w[n] > c: result = knp(n-1, c) else: temp1 = v[n] + knp(n-1, c-w[n]) temp2 = knp(n-1, c) if temp1 > temp2: result = temp1 keep[n] = 1 else: result = temp2 arr[n][c] = result return result print(knp(5,10)) # output: 16 print(keep) # [0, 1, 1, 1, 1, 0]