一个背包总容量为W, 现在有N个物品, 第i个物品容量为weight[i], 价值为value[i], 现在往背包里面装东西, 怎样装才能使背包内物品总价值最大.主要分为3类：
-
0-1背包, 每个物品只能取0个,或者1个.
-
完全背包, 每个物品可以取无限次.
-
多重背包, 每种物品都有个数限制, 第i个物品最多可以为num[i]个.
动态规划的基本思路：
将该问题转换成子问题，考虑五件物品在给定承重 C 的背包下最大价值为原问题，如下表所示，即为考虑abcde，C = 10时的最大价值， 假设为f[5][10]，原问题的解可以分解为两种情况，第一种情况是不考虑放入a只考虑放入bcde承重为C时的最大价值f[4][C],第二种情况是考虑放入a时的最大价值， 即
value[a]+f[4][10-weight[a]]。
原问题的解f[5][10]取上述两种情况中的最大值，即
f[5][10] = max{f[4][10], (f[4][10-weight[a]+value[a]))}。
以此类推，自顶向下的分析可以看出原问题需要子问题的解，我们需要先计算出子问题的解，自底向上求解。求解方式如下表所示，顺序是自底向上、从左往右， 或者从左往右、自底向上都可以。注意此问题中的abcde可以包含相同的物件，它们之间的顺序也可以是任意的，不影响最终的结果.
def _01_Knapsack(W,wt,vals,N):
"""
W: 包的总重量
wt: 每个元素的重量列表
vals: 每个元素的价值列表
N: 元素个数
"""
# 初始化dp[N+1][V+1]为0, dp[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for n in range(1,N+1):
for w in range(1,W+1):
#总容量w大于等于物品n的容量时，要考虑物品n
if wt[n-1] <= w:
# 注意由于weight、value数组下标从0开始，第n个物品的容量为wt[n-1],价值为val[n-1]
dp[n][w] = max(dp[n-1][w-wt[n-1]]+vals[n-1],dp[n-1][n])
# 总容量w小于物品n的容量时，直接不考虑物品n
else:
dp[n][w] = dp[n-1][w]
return dp
if __name__ == '__main__':
N=5
W=10
wt=[2,2,6,5,4]
vals=[6,3,5,4,6]
print(_01_Knapsack(W,wt,vals,N))
#output:
[[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, 6, 6, 11, 11, 14],
[0, 0, 6, 6, 9, 9, 9, 10, 10, 13, 13],
[0, 0, 6, 6, 9, 9, 12, 12, 15, 15, 15]]
完全背包问题描述：有编号分别为a,b,c,d的四件物品，它们的重量分别是wt = 2,3,4,7，它们的价值分别是val = 1,3,5,9，每件物品数量无限个，现 在给你个承重为W=10的背包，如何让背包里装入的物品具有最大的价值总和？
完全背包问题与01背包问题的区别在于每一件物品的数量都有无限个，而01背包每件物品数量只有一个。
如果我们用和01背包一样的状态，f[i][W]表示前i种物品恰放入一个重量为W的背包的最大价值，那我们应该用k表示当前容量下可以装第i种物品的件数， 那么k的范围应该是0≤k≤W/wt[i].既然要用当前物品i把当前容量装满，那需要0≤k≤W/wt[i]件，其中k表示件数。
状态转移方程为：
f[i][j] = max{f[i-1][W],f[i-1][W - k * wt[i]] + k * val[i]} (0<=k*wt[i]<=v)
def CompleteKnapsack(W,wt,vals,N):
"""
W: 包的总重量
wt: 每个元素的重量列表
vals: 每个元素的价值列表
N: 元素个数
"""
# 初始化dp[N+1][V+1]为0, dp[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for n in range(1,N+1):
for w in range(1,W+1):
dp[n][w] = dp[n-1][w] # k = 0时最大
for k in range(int(w/wt[n-1] + 1)):# w/wt[n-1]表示物品n最多可以取多少次,即系数
if dp[n][w] < dp[n-1][w - k*wt[n-1]] + k*vals[n-1]:
dp[n][w] = dp[n-1][w - k*wt[n-1]] + k*vals[n-1]
return dp
N=5
W=10
wt=[2,2,6,5,4]
vals=[6,3,5,4,6]
CompleteKnapsack(W,wt,vals,N)
# output:
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 6, 6, 12, 12, 18, 18, 24, 24, 30],
[0, 0, 6, 6, 12, 12, 18, 18, 24, 24, 30],
[0, 0, 6, 6, 12, 12, 18, 18, 24, 24, 30],
[0, 0, 6, 6, 12, 12, 18, 18, 24, 24, 30],
[0, 0, 6, 6, 12, 12, 18, 18, 24, 24, 30]]
优化：
让f[i][j]表示出在前i种物品中选取若干件物品放入容量为j的背包所得的最大价值。
所以说，对于第i件物品有放或不放两种情况，而放的情况里又分为放1件、2件、......W/wt[i]件.
如果不放那么 f[i][j]=f[i-1][j] ；如果确定放，那么当前背包中应该出现 至少一件第i种物品 ，所以 f[i][j]中至少应该出现一件第i种物品,即f[i][j]=f[i][j-W[i]]+val[i].
因为我们要把当前物品i放入包内，因为物品i可以无限使用，所以要用f[i][j-W[i]]；如果我们用的是f[i-1][j-W[i]]，f[i-1][j-W[i]]的意思是说，我们只有一件当前物品i，所以我们在放入物品i的时候需要考虑到第i-1个物品的价值(f[i-1][j-W[i]])；但是现在我们有无限件当前物品i，我们不用再考虑第i-1个物品了，我们所要考虑的是在当前容量下是否再装入一个物品i，而[j-W[i]]的意思是指要确保f[i][j]至少有一件第i件物品，所以要预留W[i]的空间来存放一件第i种物品。总而言之，如果放当前物品i的话，它的状态就是它自己"i"，而不是上一个"i-1"。
所以状态转移方程为：
f[i][j]=max(f[i-1][j],f[i][j-W[i]]+val[i])
def Complete_knapsack2(W, wt, val, n):
#建立n行W列数组
dp = [[0 for _ in range(W+1)]for _ in range(n)]
for i in range(0,n):
for w in range(1,W+1):
if(wt[i]<=w):
dp[i][w] = max(val[i]+dp[i][w-wt[i]],dp[i-1][w])
else:
dp[i][w] = dp[i-1][w]
#return dp[n-1][w] #返回最大值
return dp #返回结果数组
多重背包和01背包、完全背包的区别：多重背包中每个物品的个数都是给定的，可能不是一个，绝对不是无限个。
多重背包是每个物品有不同的个数限制，如第i个物品个数为num[i]。
同样可以用f[i][w]表示前i间物品恰放入一个容器为w的背包可以获得的最大价值，且每个物品数量不超多num[i]。则其状态转移方程为：
*f[i][w] = max{f[i-1][W],f[i-1][W-kwt[i]]+kval[i]} ,其中(0<=k<=min{W/wt[i], num[i]})
状态转移方程与完全背包相似，只是在选择系数k时加以限制。
def MultipleKnapsack(W,wt,vals,nums,N):
"""
W: 包的总重量
wt: 每个元素的重量列表
vals: 每个元素的价值列表
nums: 每个元素的个数列表
N: 元素个数
"""
# 初始化dp[N+1][V+1]为0, dp[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for n in range(1,N+1):
for w in range(1,W+1):
# 对于物品n最多能取的次数是w/weight[n-1]与nums[n-1]中较小者
num = min(w/wt[n-1],nums[n-1])
dp[n][w] = dp[n-1][w] # 初始取k=0为最大
for k in range(int(num) + 1):
if dp[n][w] < dp[n-1][w - k*wt[n-1]] + k*vals[n-1]:
dp[n][w] = dp[n-1][w - k*wt[n-1]] + k*vals[n-1]
return dp
N=5
W=15
wt=[5,4,7,2,6]
vals=[12,3,10,3,6]
nums=[2,4,1,5,3]
MultipleKnapsack(W,wt,vals,nums,N)
#output:
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 12, 12, 12, 12, 12, 24, 24, 24, 24, 24, 24],
[0, 0, 0, 0, 3, 12, 12, 12, 12, 15, 24, 24, 24, 24, 27, 27],
[0, 0, 0, 0, 3, 12, 12, 12, 12, 15, 24, 24, 24, 24, 27, 27],
[0, 0, 3, 3, 6, 12, 12, 15, 15, 18, 24, 24, 27, 27, 30, 30],
[0, 0, 3, 3, 6, 12, 12, 15, 15, 18, 24, 24, 27, 27, 30, 30]]