背包问题来源于生活，例如我们有一个容量有限的背包，现在有价格和重量不同的物品，如何组合才能让背包包含的物品总价格最大。如果每种物品只能选0次或1次，这样归纳为0-1背包问题。
为了简化，我们只考虑无界背包问题，也就是不限制物品的数量，如果要限制就是有界背包问题了。
这也是一个动态规划问题，是否放置第i个物品，需要取决于背包中已经考虑的i-1时的所有情况，而与前面最大子数组和不同的是，这需要考虑i和容量二维变量。
我们假设物品数量是number，背包总容量是capacity，第i件物体价值（value）和重量（weight）分别是Vi、Wi，然后第i件物理的价值（result）是Ri。
唯一的算法就用数学表达就是R[i,w] = max{ R[i-1,w], R[i-i,w-Wi] + Vi }，因此我们需要定义变量来记录每个i和每个剩余容量v时的值，这些子集结果可以复用因此适合动态规划的场景。
算法应该是这样，定义一个二维数组保存中间结果，for循环遍历物品i，for循环遍历剩余容量v，里面记录背包当时的最大价值。
首先我们来定义这些题目的变量，物品数量是number，背包容量是capacity，重量的数组是weight_array，收益的数组是value_array。
number = 5
capacity = 10
weight_array=[2,2,6,5,4]
value_array=[6,3,5,4,6]
def zero_one_pack(n, c, w, v):
# n is number
# c is capacity
# w is weight_array
# v is value_array
pass
zero_one_pack(number, capacity, weight_array, value_array)
# Print nothing
然后开始两个循环，首先循环i个物品，然后循环w的剩余空间，注意需要判断是否还有空间，如果没有空间只能和以前一样，如果有剩余空间就max一下。最后的result其实是一个二维数组，第一位是第i个物品，第二是剩余空间w，而值是那种情况下的背包最大价值。
number = 5
capacity = 10
weight_array=[2,2,6,5,4]
value_array=[6,3,5,4,6]
def zero_one_pack(n, c, w, v):
# n is number
# c is capacity
# w is weight_array
# v is value_array
result=[[0 for j in range(c+1)] for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, c+1):
if j < w[i-1]:
result[i][j] = result[i-1][j]
else:
result[i][j] = max(result[i-1][j], result[i-1][j-w[i-1]] + v[i-1])
return result
zero_one_pack(number, capacity, weight_array, value_array)
# Print the matrix of max value
'''
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 6],
[0, 0, 6, 6, 9, 9, 9, 9, 9, 9, 9],
[0, 0, 6, 6, 9, 9, 9, 9, 11, 11, 14],
[0, 0, 6, 6, 9, 9, 9, 10, 11, 13, 14],
[0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]]
'''
最后还遗留一个问题，怎样才知道放了什么东西进去，这个必须是逆推的。其实可以通过判断，如果因为这个i导致与i-1的不同，也就是相同capacity下背包的最大值不同，也就是这个i-1被选中了。这里需要一个循环遍历所有item，从头开始或者从最后开始都可以。
# Get the selected objects
selection_array = [False for x in range(n)]
capacity = c
for i in range(1, n+1):
if result[i][capacity] > result[i-1][capacity]:
selection_array[i-1] = True
capacity -= w[i-1]
print(i-1)
这是本章内容，希望对你有所帮助。进入下一章