背包问题（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)
参考链接：
完全背包
完全背包(Complete Pack):有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种背包时所得的价值，这里我们要添加的不是前一个背包，而是当前背包。所以我们要考虑的当然是当前状态。
参考链接：
多重背包
多重背包(Multiple Pack):有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]}
其他参考：
