问题描述：
有 N 件物品和一个容量为 C 的背包。第 i 件物品的重量是 wi，价值是 vi。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。如：
物品 i | 重量 w | 价值 v |
|---|---|---|
1 | 2 | 3 |
2 | 3 | 4 |
3 | 4 | 5 |
4 | 5 | 6 |
其中 N = 4，C = 8， 则最大价值为 10（即把物品 2 和 4 放入背包）。
解题思路：
01-背包问题适合用动态规划求解，用 dpi 表示前 i 个物品放入容量为 j 的背包中的最大价值，因此此问题变成一个填表问题。如上述例子，dp4 就是最后的答案。
关键是找到状态转移方程。假设现在要计算 dpi，那么分为两种情况：
- 如果当前容量 j 小于第 i 件物品的重量（j < wi），则说明第 i 件物品肯定无法放入背包，那么此背包还是只有前 i-1 个物品，即
dp[i][j] = dp[i-1][j]。 - 如果当前容量 j 大于等于第 i 件物品的重量（j ≥ wi），则说明第 i 件物品有放入背包的基本条件。那么到底能不能放要取决于第 i 件物品的加入能否使得总价值最大。如果不能最大化总价值，那么还是
dp[i][j] = dp[i-1][j]，表示不放入第 i 件物品；如果可以最大化总价值，那么dp[i][j] = dp[i-1][j-w[i]] v[i]，这里的dp[i-1][j-w[i]]为装入第 i 件物品之前的状态。
如上述例子，从上到下填表如下（第一行和第一列为边界条件初始化）：
Python3 实现：
代码语言：javascript复制class Solution:
def knapsack01(self, N, w, v, C):
'''
@param N: int, 物品总数
@param w: List, 物品重量
@param v: List, 物品价值
@param C: int, 背包容量
'''
dp = [[0] * (C 1) for _ in range(N 1)]
for i in range(1, N 1):
for j in range(1, C 1):
if j < w[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] v[i-1])
return dp[-1][-1]
N = 4
w = [2,3,4,5]
v = [3,4,5,6]
C = 8
print(Solution().knapsack01(N, w, v, C)) # 10与01-背包相关的Leetcode题目：
416：判断一个数组是否可以划分成两个相等的子集和
