后无效性原则：当前状态只与上一个状态有关
0-1背包
给定n种物品和一个容量为c的背包，物品i的重量是wi,其价值为vi。
应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大
dp[i][j]代表背包中的价值，其中i代表物品，j代表物品的容量
dp[1][0]代表容量为0时，拿第一个物品的价值是多少
j<w[i],代表物体的重量比背包的容量大，不足以放入背包，所以不放入该包中，现在背包中的价值为dp[i][j]=dp[i-1][j]
j>=w[i],如果不拿，dp[i][j]=dp[i-1][j],如果拿了dp[i-1][j-w[i]]+c[i](上一个的价值加上拿了这个的价值）

1.png

# 输入的方式是列表
# 如[1,2,3]
# slist = eval(input())
# [1, 2, 3] <class 'list'>
# print(slist,type(slist))

wlist = []
vlist = []
tall = [int(i) for i in input().split()]
print(tall)

while True:
    templist = []
    temp = input().split()
    if temp:
        list1 = [int(i) for i in temp]
        wlist.append(list1[0])
        vlist.append(list1[1])
    else:
        break
print(wlist)
print(vlist)
wlist = [0]+wlist
vlist = [0]+vlist
dp = [[0 for _ in range(tall[0]+1)] for _ in range(tall[1]+1)]
print(dp)

# 遍历每个物体
for i in range(1,tall[1]+1):
    # 遍历背包容量的所有可能
    for j in range(1,tall[0]+1):
        # 当背包的容量小于物品的质量时
        if j<wlist[i]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-wlist[i]]+vlist[i])

print(dp)

滚动数组

wlist = []
vlist = []
tall = [int(i) for i in input().split()]
print(tall)

while True:
    templist = []
    temp = input().split()
    if temp:
        list1 = [int(i) for i in temp]
        wlist.append(list1[0])
        vlist.append(list1[1])
    else:
        break
print(wlist)
print(vlist)
wlist = [0]+wlist
vlist = [0]+vlist
# dp = [[0 for _ in range(tall[0]+1)] for _ in range(tall[1]+1)]
dp = [0]*(tall[0]+1)

# 遍历每个物体
for i in range(1,tall[1]+1):
    # 遍历背包容量的所有可能
    for j in range(tall[0],0,-1):
        # 当背包的容量小于物品的质量时
        if j>=wlist[i]:
            dp[j] = max(dp[j],dp[j-wlist[i]]+vlist[i])
print(dp)
#  [0, 0, 1, 3, 5, 5, 6, 9, 9, 10, 12]

完全背包问题
设有n种物品，每种物品有一个重量及一个价值，但每种物品的数量是无线的，同时有一个背包，最大载重为M，今从n中物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
朴素算法

wlist = []
vlist = []
tall = [int(i) for i in input().split()]
print(tall)

while True:
    templist = []
    temp = input().split()
    if temp:
        list1 = [int(i) for i in temp]
        wlist.append(list1[0])
        vlist.append(list1[1])
    else:
        break
print(wlist)
print(vlist)
wlist = [0]+wlist
vlist = [0]+vlist
# dp = [[0 for _ in range(tall[0]+1)] for _ in range(tall[1]+1)]
dp = [0]*(tall[0]+1)

# 遍历每个物体
for i in range(1,tall[1]+1):
    # 遍历背包容量的所有可能
    for j in range(tall[0],0,-1):
        for k in range(j//wlist[i]+1):
            # 当背包的容量小于物品的质量时
            if j>=wlist[i]:
                dp[j] = max(dp[j],dp[j-k*wlist[i]]+k*vlist[i])
print(dp)

优化算法
状态转移方程
dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+c[i]]

wlist = []
vlist = []
tall = [int(i) for i in input().split()]
print(tall)

while True:
    templist = []
    temp = input().split()
    if temp:
        list1 = [int(i) for i in temp]
        wlist.append(list1[0])
        vlist.append(list1[1])
    else:
        break
print(wlist)
print(vlist)
wlist = [0]+wlist
vlist = [0]+vlist
# dp = [[0 for _ in range(tall[0]+1)] for _ in range(tall[1]+1)]
dp = [0]*(tall[0]+1)

# 遍历每个物体
for i in range(1,tall[1]+1):
    # 遍历背包容量的所有可能
    for j in range(1,tall[0]+1): #顺序推
            # 当背包的容量小于物品的质量时
            if j>=wlist[i]:
                dp[j] = max(dp[j],dp[j-wlist[i]]+vlist[i])
print(dp)

优化代码：

# 遍历每个物体
for i in range(1,tall[1]+1):
    # 遍历背包容量的所有可能
    for j in range(wlist[i],tall[0]+1): #顺序推
            # 当背包的容量小于物品的质量时
        dp[j] = max(dp[j],dp[j-wlist[i]]+vlist[i])
print(dp)

多重背包
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求正解将那些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
背包问题区别：0-1背包是没见只有1件，完全背包是每种无限件，完全背包是每件无限件，而多重背包是每件有限件。