推荐阅读：

百度百科：https://baike.baidu.com/item/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/2416931?fr=aladdin#reference-[9]-841810-wrap

java实现：https://blog.csdn.net/Cobbyer/article/details/108127742

计算机常用算法与程序设计案例教程： https://max.book118.com/html/2019/0122/6053000055002003.shtm

知乎：https://zhuanlan.zhihu.com/p/93857890

1 0-1背包

对于输入

4件物品 背包能承受的最大重量为10

单体重量2 单体价值1

单体重量3 单体价值3

...

python
4 10
1 1
3 3
4 5
7 9

动态规划：

python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
# 创建二维list
dp = []
for i in range(N + 1):
    dp.append([])
    for j in range(V + 1):
        dp[i].append(0)
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for j in range(1, V + 1):  # 表示当前背包的容量为j
        if j < w[i]:  # 如果当前背包容量j放不下重量为w[i]的物体
            dp[i][j] = dp[i - 1][j]  # 不拿 i 物品，此时背包价值依旧等于成功拿了上一个物体时的价值
        else:
            # 背包装得下，但是考虑一下值不值得拿，比较一下拿了和没拿前后背包价值的变化，取最大的方法
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i])
# 打印二维list
for i in range(len(dp)):
    print(dp[i])

输出dp：

python
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 3, 4, 4, 4, 4, 4, 4, 4]
[0, 1, 1, 3, 5, 6, 6, 8, 9, 9, 9]
[0, 1, 1, 3, 5, 6, 6, 9, 10, 10, 12]

dp表中每一个dp[i]的值只与dp[i-1]有关系，即后无效性原则。

dp[i][j]表示前i件物品恰放入一个容量为j的背包可以获得的最大价值。

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]) 表示 考虑一下值不值得拿，比较一下拿了和没拿前后背包价值的变化，取最大的方法。

整个dp只有最终的dp[N][V] 有意义，其他数据都是为了求出dp[N][V] 而做的变化。

改进代码：

python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
dp = [0 for i in range(V + 1) ]
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for j in range(V, 0, -1):  # 从后往前推
        if j >= w[i]:  # 如果当前背包容量j 可以放下 重量为w[i]的物体
            dp[j] = max(dp[j], dp[j - w[i]] + c[i])
    print(dp)

2 完全背包

问题描述：给定 N 种物品每种物品都有无限件可用，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
# 创建二维list
dp = []
for i in range(N + 1):
    dp.append([])
    for j in range(V + 1):
        dp[i].append(0)
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for v in range(1, V + 1):  # 表示当前背包的容量为j
        dp[i][v]=0
        # 最多可以放nCount个物品i
        nCount = v // w[i]
        # 和01背包的区别就在这里，01
        # 背包只有两种状态：放与不放
        # 而完全背包可以放0到k个物品i，同样是取最大值
        for k in range(nCount+1):
            dp[i][v] = max(dp[i][v], dp[i - 1][v - k * w[i]] + k * c[i]) 
# 打印二维list
for i in range(len(dp)):
    print(dp[i])

输入：

python
4 5
1 2
2 4
3 4
4 5

输出

python
[0, 0, 0, 0, 0, 0]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]

3 多重背包

问题描述：给定 N 种物品每种物品 i 都有 s[i] 件可用，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

python
numandweight = list(map(int, input().split(' ')))  # 读取输入
N = numandweight[0]  # N件物品
V = numandweight[1]  # 背包能承受的最大重量为V
w = [0]  # 第一个元素无用  单体重量
c = [0]  # 第一个元素无用  单体价值
s = [0]  # 第一个元素无用  有多少件
for i in range(N):
    temp = list(map(int, input().split(' ')))  # 读取输入
    w.append(temp[0])
    c.append(temp[1])
    s.append(temp[2])
# 创建二维list
dp = []
for i in range(N + 1):
    dp.append([])
    for j in range(V + 1):
        dp[i].append(0)
for i in range(1, N + 1):  # 表示当前有第i个物品可以拿
    for j in range(V,-1,-1 ):  # 表示当前背包的容量为j
        for k in range(0, s[i] + 1):
            if j>=k * w[i]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * c[i])
# 打印二维list
for i in range(len(dp)):
    print(dp[i])

输入

python
4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出

python
[0, 0, 0, 0, 0, 0]
[0, 2, 4, 6, 6, 6]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]
[0, 2, 4, 6, 8, 10]