01背包
01背包作为背包问题的鼻祖，也是所有背包问题的基础，其一般形式如下。
给你 \(n\) 个物品和一个容量为 \(m\) 的背包，每件物品有他的价值 \(v_i\) 与他的质量 \(w_i\) 。
乍一看，这类题似乎可以使用贪心进行解答，但很容易给出一个反例：
3 10
5 8
5 8
6 10
注：该样例每个物品的 \(w_i\) 在前 \(v_i\) 在后。
从贪心的角度上来讲，应该从大到小依次取 \(\frac{v_i}{w_i}\) 值最大的数，也就是仅仅取第三个物品，但很显然，我们应该取第一个和第二个物品来获得最大的价值16。
这时候我们便可以引出01背包了，我们很容易可以发现，每一个物品的状态只有两种情况，选1与不选0，那么假定 \(dp_{i,j}\) 表示前 \(i\) 个数中花费 \(j\) 的背包容量时所能达到的最大的价值和，便可以轻松的想出两个状态的贡献。
若不选（0），则 \(dp_{i,j} = dp_{i - 1,j}\) 。
若选择（1），则 \(dp_{i,j} = dp_{i - 1,j - w_i} + v_i\) 。
那么我们在推出这连个式子之后便可以轻松的得出转移方程，也就是 \(dp_{i,j} = \max(dp_{i - 1,j},dp_{i - 1,j - v_i} + w_i)\) 。
优化
我们可以发现实际上每一次计算时仅仅与 \(dp_{i}\) 和 \(dp_{i - 1}\) 有关，所以我们可以考虑使用滚动数组进行优化来优化掉一位是的空间复杂度达到 \(O(m)\) 而此时一个细节便是枚举 \(j\) 时要倒序枚举，原因如下。
我们假设当前正序枚举到了 \(k\) ，那么 \(1 - k\) 之间便是更新后 \(i\) 的值，\(k + 1\) 到 \(n\) 之间的值为更新前的 \(i - 1\) 。由于我们需要从 \(i - 1\) 转移到 \(i\) ，所以正序枚举是WA掉的，按照上述的方法在推一遍倒序枚举，我们就会发现倒序枚举完美符合我们的需求。所以第 \(i\) 个数选与不选对答案的贡献就出来了：
不选（0）：\(dp_j = dp_j\) 。
选（1）：\(dp_j = dp_{j - v_i} + w_i\) 。
所以转移方程就是 \(dp_j = \max(dp_j,dp_{j - v_i} + w_i)\) 。
代码就不给了，相信大家看到了转移方程以后就都会了。
多重背包
多重背包的题型和01背包一样，给你 \(n\) 个物品和一个容量为 \(m\) 的背包，每个物品有他的重量 \(v_i\) 价值 \(w_i\) ，数量 \(s_i\) 。显然，多重背包和01背包的最大区别就是每个物品可以选 \(s_i\) 次。我们考虑把这个问题转化为01背包，我们可以把第 \(i\) 个物品选 \(k\) 次所达成的贡献看作一个全新的物品，那么一个可以取 \(s\) 次的物品就可以转化为 \(s\) 个单独的物品，所以我们可以使用三重循环，第一层第二层枚举与01背包相同，第三层枚举选举物品的数量，我们可以很轻松的得到转移方程：
\(dp_{i,j} = \max(dp_{i - 1,j},dp_{i - 1,j - v_i * k} + w_i * k)\)