动态规划之背包问题

背包问题（Knapsack problem）是动态规划的经典问题。动态规划的基础是递归，和分治一样，都是假设子问题已经解决，由子问题的解组合计算得到父问题的解，类似裴波那契数列中的递推式如f(n) = f(n-1) + f(n-2)。但在递归的过程中会出现重复计算子问题的现象，为了避免重复计算，用一个表格记录子问题的结果供查找，从下往上进行递推。找递推式（or 状态转移方程）的思路一般是由最终状态往前回溯，考察解答最终问题需要哪些子问题。

背包问题，有很多中类型，常见的有：

• 01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包， 每种物品均只有一件 。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
• 完全背包(CompletePack): 有N种物品和一个容量为V的背包， 每种物品都有无限件可用 。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
• 多重背包(MultiplePack): 有N种物品和一个容量为V的背包， 第i种物品最多有n[i]件可用 。每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

01背包

动态规划的核心过程有两部分，一个是找出问题的“子状态”，再一个就是建立“状态转移方程”（所谓的递推公式）。欲求背包能够获得的总价值，即求前i个物体放入容量为m背包的最大价值c[i][m]

• w[i]：第i个物体的重量
• p[i]：第i个物体的价值
• c[i][j]：前i个物体放入容量为j 包的最大价值
• c[i-1][j]：前i-1个物体放入容量为j 包的最大价值
• c[i-1][j-w[i]]：前i-1个物体放入容量为j-w[i] 包的最大价值

以下通过表格来说状态转移方程：

c[i][m]=max{c[i-1][m-w[i]]+p[i],c[i-1][m]}

这里是用二维数组存储的，可以把空间优化，用一维数组存储。 用c[0..m]表示，c[m]表示把前i件物品放入容量为m的背包里得到的价值。把i从1~n(n件)循环后，最后c[m]表示所求最大值。

这里c[m]就相当于二维数组的c[i][m]。那么，如何得到c[i-1][m]和c[i-1][m-w[i]]+p[i]？

首先要知道，我们是通过i从1到n的循环来依次表示前i件物品存入的状态。即：for i=1..N。现在思考如何能在是c[m]表示当前状态是容量为m的背包所得价值，而又使c[m]和c[m-w[i]]+p[i]标签前一状态的价值？

答案是逆转：

for i=1..N
   for m=V..0
        c[m]=max{c[m],c[m-w[i]]+p[i]};

分析上面的代码：当内循环是逆序时，就可以保证后一个c[m]和c[m-w[i]]+p[i]是前一状态的！这里给大家一组测试数据：

相关代码实现：

#A naive recursive implementation of 0-1 Knapsack Problem
 
# Returns the maximum value that can be put in a knapsack of
# capacity W
def knapSack(W , wt , val , n):
 
    # Base Case
    if n == 0 or W == 0 :
        return 0
 
    # If weight of the nth item is more than Knapsack of capacity
    # W, then this item cannot be included in the optimal solution
    if (wt[n-1] > W):
        return knapSack(W , wt , val , n-1)
 
    # return the maximum of two cases:
    # (1) nth item included
    # (2) not included
    else:
        return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1),
                   knapSack(W , wt , val , n-1))
 
# end of function knapSack
 
# To test above function
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print knapSack(W , wt , val , n)
 
# This code is contributed by Nikhil Kumar Singh.

以上方法的时间和空间复杂度为O(n*W)，其中时间复杂度已经不能再优化了，但是空间复杂度可以优化到O(W)，优化后的代码如下：

# A Dynamic Programming based Python Program for 0-1 Knapsack problem
# Returns the maximum value that can be put in a knapsack of capacity W
def knapSack(W, wt, val, n):
    K = [[0 for x in range(W+1)] for x in range(n+1)]
 
    # Build table K[][] in bottom up manner
    for i in range(n+1):
        for w in range(W+1):
            if i==0 or w==0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
 
    return K[n][W]
 
# Driver program to test above function
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))
 
# This code is contributed by Bhavya Jain

上述代码实现为01背包问题的实现原理，如需在实际情况中采用类似的思路解决问题，可以使用Google Optimization Tools工具，具体代码如下：

from ortools.algorithms import pywrapknapsack_solver
 
weights = [[565, 406, 194, 130, 435, 367, 230, 315, 393,
            125, 670, 892, 600, 293, 712, 147, 421, 255]]
capacities = [850]
values = weights[0]
 
# Create the solver.
solver = pywrapknapsack_solver.KnapsackSolver(pywrapknapsack_solver.KnapsackSolver.KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER,
                                              'test')
 
solver.Init(values, weights, capacities)
computed_value = solver.Solve()
 
packed_items = [x for x in range(0, len(weights[0]))
                if solver.BestSolutionContains(x)]
packed_weights = [weights[0][i] for i in packed_items]
 
print("Packed items: ", packed_items)
print("Packed weights: ", packed_weights)
print("Total weight (same as total value): ", computed_value)

参考链接：

• https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
• https://developers.google.com/optimization/bin/knapsack

完全背包

完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的重量为w [i]，价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。完全背包按其思路仍然可以用一个二维数组来写出：

c[i][m]=max{c[i-1][m-k*c[i]]+k*p[i] | 0<=k*c[i]<=m }

同样可以转换成一维数组来表示:

for i=1..N
    for m=0..V
        c[m]=max{c[m],c[m-w[i]]+p[i]}

完全和01背包的区别，这里的内循环是顺序的，而01背包是逆序的。为何完全背包可以这么写？原因是为了max中的两项是前一状态值。那么这里，我们顺序写，这里的max中的两项当然就是当前状态的值了，为何？ 因为每种背包都是无限的。当我们把i从1到N循环时，c[m]表示容量为m在前i种背包时所得的价值，这里我们要添加的不是前一个背包，而是当前背包。所以我们要考虑的当然是当前状态。

参考链接：

• http://www.wutianqi.com/?p=539

多重背包

多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件重量是w[i]，价值是p[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：

c[i][m]=max{c[i-1][m-k*w[i]]+k*p[i]|0<=k<=n[i]}

其他参考：

• http://novoland.github.io/%E7%AE%97%E6%B3%95/2014/07/26/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98.html