考前两天，再看一下dd的背包九讲，巩固一下。（毕竟我DP实在是太弱了）
01背包
模型
有(N)个物品，每个费用为(V_i)，价值为(W_i)，总钱数为(C)，求最大价值。
子状态
(f[i][j])表示前(i)件总钱数为(j)情况下的最大价值。
朴素转移
朴素转移每一次讨论当前物品到底取不取。
状态转移方程为(f[i][j]=min(f[i-1][j],f[i-1][j-w[i]]+v[i]))
空间优化
由于每一层的取值只需要依赖上一层的值，因此在实现的时候可以省略第一维。
但是这个时候原第二位的遍历需要采取倒叙，这样就可以保证我们遍历到(f[j])的时候(f[j-w[i]])里面保存的是原来(f[i-1][j-w[i]])的值。
伪码实现
FOR i from 0 to C
f[0][i]=0
FOR i from 1 to n
FOR j from Vi to C
f[i][j]=min(f[i-1][j],f[i-1][j-w[i]]+v[i])
FOR i from 0 to C
f[i]=0
FOR i from 1 to n
FOR j from C downto Vi
f[j]=min(f[j],f[j-w[i]]+v[i])
细节
如果题目不要求背包要恰好装满，那么照常初始化。
但如果要求背包恰好装满，那么(f[1])到(f[C])都必须设为(-INF)（因为只有(f[0])是刚好装满），而最后的答案为(f[C])。
完全背包
模型
有(N)种物品，每种都有无限个，其余同01背包。
子状态
考虑01背包的空间优化写法，我们发现，之所以不可以顺序写，是因为这样同样的一件物品可能会被取多次。
这恰好是完全背包问题所允许的。
因此完全背包问题采用顺序的写法。
子状态为(f[i])，表示容量为(i)的背包最多能放多少个。
转移
上面说了
代码实现
FOR i from 0 to C
f[i]=0
FOR i from 1 to n
FOR j from Vi to C
f[j]=min(f[j],f[j-w[i]]+v[i])