1、01背包问题
物品个数N，背包总体积V
0<=N<=1000,0<=V<=1000
f[i][j]:表示只看前i个物品，总体积是j的情况下，总价值是多少。
result = max{f[N][0~V]}
V[i]:第i个物品的体积
w[i]：第i个物品的价值
f[i][j] # 状态数n2个
# 转移复杂度：O(1)的，没有循环
1 不选第i个物品,f[i][j] = f[i-1][j]
2 选第i个物品,f[i][j] = f[i-1][j-V[i]]
3 取最大值,f[i][j] = max{1. 2}
初始化：f[0][0] = 0 # 在没有选任何物品的情况下，体积是0的情况下，最大价值为0.
总时间复杂度：O(NV) 1000000
空间复杂度:O(NV) 1000000
# 为什么1000000是OK呢？
C++中，一百万个int，一个int4个字节：4*1000000/1024/1024=3.8MB=4MB
二维的动态规划：
#### python3代码：二维数组
import sys
N = 1010
V = [0]*N # 每个物品的体积
W = [0]*N # 每个物品的价值
f = [[0 for i in range(N)] for j in range(N)] # dp数组
f[0][0] = 0
# 1、读入数据，并通过map函数转化为需要的类型
# 第一行，表示物品数量和背包容积
n, v = map(int, sys.stdin.readline().split())
for i in range(1, n+1):
# 读入第i件物品的体积和价值
V[i], W[i] = map(int, sys.stdin.readline().split())
for i in range(1,n+1): # i从1到n
for j in range(1, v+1):# j从1到v
f[i][j] = f[i-1][j]# 不选第i个
if (j >= V[i]):# 选第i个物品时，从选择了第i个物品的状态和前面的状态中取最大价值。
f[i][j] = max(f[i][j], f[i-1][j-V[i]]+W[i])
print(f[n][v])
#### python3代码：优化为一维数组
import sys
N = 1010
V = [0]*N # 每个物品的体积
W = [0]*N # 每个物品的价值
f = [0 for j in range(N)] # 一维dp数组
f[0] = 0
# 1、读入数据，并通过map函数转化为需要的类型
# 第一行，表示物品数量和背包容积
n, v = map(int, sys.stdin.readline().split())
for i in range(1, n+1):
# 读入第i件物品的体积和价值
V[i], W[i] = map(int, sys.stdin.readline().split())
for i in range(1,n+1): # i从1到n
for j in range(v,0,-1):# j从v到1
if (j >= V[i]):# 选第i个物品
f[j] = max(f[j], f[j-V[i]]+W[i])
print(f[v])# f[v]：表示体积小于等于v的情况下，最大价值是多少。
从二维转一维:
因为$f[i][j] = max(f[i][j], f[i-1][j-V[i]]+W[i])$是用前$i-1$个物品的装大小为$j-V[i]$的背包的最大价值，来更新$f[i][j]$，所以j需要从v到1遍历，逆序遍历，这样$f[v] = max(f[v], f[v-V[i]]+W[i])$就可以用到$f[v-V[i]]$的值来更新$f[v]$。
python代码注意事项：
range(1, n+1):等价于[1,n]
range(n, 0, -1):等价于[n,1]
背包问题初始化细节：
1、求恰好装满背包时的最大价值的最优解：
f[0] = 0：只有容量为0的背包可以在什么也不装且价值为0的情况下被“恰好装满”
f[1…V]=-inf：而其他容量的背包均没有合法的解，属于未定义的状态，应复制为-inf（负无穷）
2、求价值最大的最优解，并没有要求把背包装满。
f[0…V]=0：如果背包并非必须被装满，那么任何容量的背包都有一个合法的解，即“什么都不装“，这个解的价值为0，所以初始状态的值也全都为0.
2、完全背包问题
01背包是每件物品可以选或不选，而完全背包是每件物品可以选择无限次。
一维空间：
状态表示：
n为物品数，v为背包大小
f[i]表示背包总体积是i的情况下的最大价值
result = max{f[0 ... v]}，答案是枚举f[0]到f[v]，取最大值。
状态转移：
从前往后考虑每个物品，
for i in range(1,n+1):
# 变成完全背包，把j的循环位置从range(v,0,-1)变为range(1,v+1)
# 从小到大去更新f[j]这个状态，f[j-V[i]]肯定是先算的，f[j-V[i]]已经考虑了选第i个物品。
for j in range(1,v+1):
if j>=V[i]:
f[j] = max(f[j],f[j-V[i]]+W[i])
# 等价于对于第i个物品，在背包容量为j时，最多能选k个
for j in range(v,0,-1):
k=0
while j>=k*V[i]:
f[j] = max(f[j], f[j-k*V[i]]+k*W[i])
k+=1
##########完整代码
import sys
N = 1010
f = [0]*N # 一维dp数组
V = [0]*N # 每个物品的体积
W = [0]*N # 每个物品的价值
f[0] = 0
# 处理输入，n个物品，v是背包大小
n,v = map(int, sys.stdin.readline().split())
for i in range(1,n+1):
V[i],W[i] = map(int, sys.stdin.readline().split())
for i in range(1,n+1):
# 下面两种都可以，任选一种:1
for j in range(1,v+1):
if j>=V[i]:
f[j] = max(f[j], f[j-V[i]]+W[i])
# 2
for j in range(V[i],v+1):# 此处默认了j>=V[i]
f[j] = max(f[j], f[j-V[i]]+W[i])
print(f[v])
数学归纳法：略（没听懂，需要再看看2. 01背包问题
01和完全背包的区别：
01背包每件物品只能用1次；完全背包每件物品可用无限次。
代码上的区别：（一维数组情况）
- 第一重循环不变，都是遍历物品，从第1件物品到第n件物品；
- 第二重循环，01背包循环体积j时，从大到小枚举；完全背包循环体积j时，从小到大枚举；
3、多重背包问题
$n$个物品，$v$是背包总体积大小
每个物品有三个属性，$V，W，S，$分别表示第$ i$种物品的体积、价值和数量。
数据范围：
$0<n,v<=100$
$0<v_i,w_i,s_i<=100$
相较于完全背包和01背包，每件物品不是数量无限了，限制数量为s个了。
多重背包是01背包问题的扩展，体积在枚举的时候要和01背包相同，从大到小枚举
三重循环，可以使用3次方复杂度的算法，$100^3$=1000000
状态表示：
f[j] 总体积是j的情况下，最大价值是多少
for i in range(1,n+1):# 遍历物品
for j in range(v,0,-1): # 从大到小，遍历背包大小
for s in range(0,S[i]+1):# 多重背包加了选s个物品的循环
if j >= s*V[i]:
# 多重背包：不选(选0个)，选1个，选2个，选s个...共有s+1中选法
f[j] = max(f[j], f[j-s*V[i]]+s*W[i])
# f[j] = max(f[j], f[j-V[i]+W[i]],f[j-2*V[i]+2*W[i]]...)
初始化与结果：
1、f[i] = 0
result = f[m]
2、f[0] = 0, f[i] = -INF, i!=0
result = max(f{0 ... m})
多重背包完整代码：
import sys
N = 110
f = [0]*N # 一维dp
V = [0]*N # 每个物品的体积
W = [0]*N # 每个物品的价值
S = [0]*N # 每个物品的数量
# 处理输入
n,v = map(int,sys.stdin.readline().split())
for i in range(1,n+1):
V[i],W[i],S[i] = map(int,sys.stdin.readline().split())
for i in range(1,n+1):
for j in range(v,0,-1):
for s in range(0,S[i]+1):
if j >= s*V[i]:
f[j] = max(f[j], f[j-s*V[i]]+s*W[i])
print(f[v])
