动态规划 - 闫式DP分析法

背包问题

1、 01背包
每件物品只有两种选择，被选和不被选
f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w);
2、完全背包
每件物品都有无限件可用，朴素版做法：枚举每一个状态选取最大值，优化做法：对代码进行恒等变形得到状态转移等式

f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, ... );
f[i][j - v] = max(f[i - 1][j - v], f[i - 1][j - 2v] + w, f[i - 1][j - 3v] + 2w, ... );
f[i][j] = max(f[i - 1][j], f[i][j - v] + w);

3、多重背包
由01背包转化而来，不同的是每件物品只有有限件，因此在状态转移计算中要多加一层循环，并且要判断k件物品的体积是否超过剩余体积j
for (int k = 1; k <= s && k * v <= j; k ++ );