背包问题

1.状态表示f(i, j)
(1)集合
    a.所有选法的集合
    b.每个集合满足的条件
        只从前i个物品物品中选
        总体积 <= j
(2)属性：max（背包问题），min，数量

2、状态计算f(N, V)
(1)集合划分：如何把当前的集合化成子集，并通过子集计算出该集合
(2)一般原则：不重不漏

如果比较的是当前层的，就从小到大
如果比较的是上一层的，就从大到小（同层前面的还未被更新）

01背包问题

f[i, j] = max(f[i - 1][j], f[i - 1][j - v[i]] + v[i])

分为两个子集
f(i, j) 包含i：1到i-1，且体积 <= j  ->  f(i - 1, j) 
        不包含i：1到i，且体积 <= j  ->  f(i - 1, j - v[i]) + w[i]

完全背包问题

f(i, j) = max(f[i - 1][j - k * v[i]] + k * w[i])

按照第i个物品选多少个来分
求max 曲线救国
(1)去掉k个物品i
(2)求max = f(i - 1)(j - k * v[i])
(3)再加回来k个物品i

多重背包问题

f[i, j] = max(f[i - 1][j - k * v[i]] + k * w[i])

分类（k的范围）
0 1 2 ... s[i]