女娲补天之背包问题
不同情况下求最值的初始化
二维情况：
1、体积至多是（不超过）j，其余全部初始化为0（f[i][j] = 0），只会求价值的最大值
2、体积恰好是j、
如果求价值的最小值：f[0][0] = 0，其余是INF
如果求价值的最大值：f[0][0] = 0，其余是-INF
3、体积至少是j，f[0][0] = 0，其余全部初始化为INF（f[i][j] = INF），只会求价值的最小值
一维情况：
1、体积至多是（不超过）j，其余全部初始化为0（f[i] = 0），只会求价值的最大值
2、体积恰好是j、
如果求价值的最小值：f[0] = 0，其余是INF
如果求价值的最大值：f[0] = 0，其余是-INF
3、体积至少是j，f[0] = 0，其余全部初始化为INF（f[i] = INF），只会求价值的最小值
不同情况下求方案数的初始化
二维情况：
1、体积至多是（不超过）j，f[0][i] = 1， 0 <= i <= m，其余都是0（从0个物品中选不超体积为j都有一种方案就是都不选）
2、体积恰好是j，f[0][0] = 1，其余都是0（前0个物品都不选，体积恰好为0这一种方案）
3、体积至少是j，f[0][0] = 1，其余都是0（同样是都不选这一种方案）
一维情况：
1、体积至多是（不超过）j，f[i] = 1， 0 <= i <= m，其余都是0
2、体积恰好是j，f[0] = 1，其余都是0
3、体积至少是j，f[0] = 1，其余都是0
参考于：小呆呆
01背包：
每个物品只能选一次，且有两个属性，体积与价值。
朴素版：第一层循环物品个数，第二层循环背包容量。
优化版：第二层从大到小循环背包容量，优化至一维
时间复杂度：O(nm)
完全背包：
每个物品可以选无数次，具有两个属性，体积与价值
朴素版：第一层循环物品种类，第二层循环背包容量，第三层循环每个物品选几个，注意不能超出目前背包体积。
优化版：第二层从小到大循环背包容量，优化至一维
并将第三层循环等价于如下公式：
二维版：f[i][j]=max(f[i−1][j],f[i][j−v]+w[i])
一维版：f[j]=max(f[j],f[j−v[i]]+w[i])
时间复杂度：O(nm)
多重背包1：
每个物品可以选有限次（s[i]次），具有两个属性，体积与价值
朴素版：第一层循环物品种类，第二层循环背包容量，第三层循环每个物品选几个，注意判断不能超出已有数量和背包体积限制。
简单优化：第二层也是从大到小循环容量，第三层使用while作为判断条件，可以用一维循环了。
时间复杂度：O(nmk)
多重背包2:
多重背包1的优化，利用二进制将背包分组，再使用01背包问题解决
时间复杂度：O(n2logS)
分组背包：
有多个组，每个组的物品有多个，每个组的物品只能选一个，每个物品具有两个属性，体积与价值
第一层循环组数，第二层循环背包容量，第三层循环决策，也就是每个组选哪个
优化：第二层背包容量从大到小循环，优化至一维
混合背包:
分成两组来计算，第一组是完全背包的情况，第二组是01背包和多重背包，01背包是特殊的多重背包。
第二组记得用二进制优化
二维费用背包：
以01背包的二维费用为例，每个物品存在三个属性，除了价值外，有体积与重量两个限制的属性。
按理来说需要一个三维数组，根据二维转一维的先例，这里可以将三维转二维
第一层循环物品个数，第二层从大到小循环体积，第三层从大到小循环重量，可以直接用二维数组来做了。
for i in range(N):
v, m, w = map(int, input().split())
for j in range(V, v - 1, - 1):
for k in range(M, m - 1, - 1):
f[j][k] = max(f[j][k], f[j - v][k - m] + w)
刷题列表
洛谷 P1049 装箱问题
太久不写背包了全是问题hh
首先是01背包的一维优化版，第二层循环是从大到小循环，但这个小不是0，而是当前这个物品的体积！！
第二就是输入到底是一行全部给出还是一行给一个看看清楚
洛谷 P1164 小A点菜
看样子是个很简单01背包问题求方案数，这里是体积（价钱）恰好为j的情况，所以需要将f[0] = 1，其余都是0。
但这里数据很坑，并不在一行内给出，所以需要写一个循环加extend！每次判断输入是否已经满了n个数
w = []
k = 0
while k < n:
w.extend(list(map(int, input().split())))
k += len(w)
洛谷 P3985 不开心的金明
1e9会爆空间，但优化看不懂，就当01背包来做了
洛谷 P2722总分 Score Inflation
完全背包，py过不去hh
洛谷 P1853 投资的最大效益
完全背包 + 套了一层循环，相当于都做一次完全背包，但需要更新每年的本金。
由于投资额都是1000的倍数，所以第二层循环的步长可以定位1000，最后累加收益的时候直接累加到最接近的一个s += f[(s // 1000) * 1000]
for year in range(n):
f = [0] * (s + 5)
for i in range(d):
for j in range(v[i], s + 1, 1000):
f[j] = max(f[j], f[j - v[i]] + w[i])
s += f[(s // 1000) * 1000]
洛谷 P1833 樱花
混合背包问题，里面的多重背包用当了二进制优化，可以对每一个二进制的k做一遍01背包，最后多出来的那部分也要。
本题时间的读入也很头疼hhh，分割成三块来一步步做。
P2347 砝码称重
虽然这是普及-，但感觉真的很坑啊
表面上来看这是一道非常简单的多重背包求方案数的问题，可以通过二进制优化转化为01背包问题.
但是！！对于普通的01背包求方案数，如果同时选择物品a和b与同时选择物品c和d获得的价值是一样的话，会被算做两种方案。但这里的价值一样就相当于能凑出的砝码重量一样，只能算作一种！！
坑死了
所以这里应该求在前i个物品中，体积不超过j的最大价值是多少，这里的体积和价值是一个东西。
最后只要统计f[i] == i的情况，也就是在前i个物品中选，体积不超过j的情况下最大价值恰好j的时候，说明f[i]是可以凑出来的，所以+1
洛谷 P5365 英雄联盟
多重背包问题（乘法） + 一维优化
本来想定义的f[i, j]是前i个皮肤中不超过j个展示策略的花费
但这个展示策略的数量实在太大了，1017，所以重新定义f[i][j]来表示前i个皮肤的j个花费的最大方案数。
注意这里需要统计一下总钱数，不单纯是相加，要乘上每个皮肤的数量
money = 0
for i in range(1, n + 1):
money += num[i] * c[i]
转移方程：
f[i][j] = max(f[i - 1][j], f[i - 1][j - p * c[i]] * p)
注意这里求方案用的是乘法捏，不再是加法了，但本题的二维状态在计算的时候有点问题，所以抛弃二维状态转为一维，本来第二维也有点大hhh
f[j] = max(f[j], f[j - p * c[i]] * p)
，并初始化f[0] = 1
转移过程，第二维从大到小
for i in range(1, n + 1):
for j in range(money, 0, -1):
k = 0
while k <= num[i] and k * c[i] <= j:
f[j] = max(f[j], f[j - k * c[i]] * k)
k += 1
这里因为是乘法，所以感觉不适合用二进制，因为比如将一个k = 1，一个k = 2，组合在一起变成这个皮肤选3个，但这里算只会有两个策略，因为1再2，所以状态是乘法的不能用二进制，简单一维优化即可。
洛谷 P1541 乌龟棋
二进制优化，单调队列随缘了
一边二进制一边转移，上下都写个转移方程，while循环中里面的for循环转移，和剩下的s[i]也需要一个for循环进行状态转移
for i in range(1, n + 1):
k = 1
while s[i] >= k:
for j in range(m, k * v[i] - 1, -1):
f[j] = max(f[j], f[j - k * v[i]] + k * w[i])
s[i] -= k
k *= 2
if s[i]:
for j in range(m, s[i] * v[i] - 1, -1):
f[j] = max(f[j], f[j - s[i] * v[i]] + s[i] * w[i])
