背包问题
背包问题有许多种，其中最简单的形如最优装载问题:给出n个物体，第i个物体的重量为wi。在总重量不超过c的前提下选择尽可能多的物体。这种问题就是最简单的贪心问题，用贪心算法就能得到最优解。
复杂一些的是部分背包问题。这类题在最优装载问题的基础上给了每个物体价值vi。也可以用贪心算法做，根据每个物体的性价比贪心就行。
0-1背包问题
而对于更复杂的0-1背包问题，背包问题就不一定能得到最优解了。这时候我们就要用到动态规划。
动态规划与分治法相似，都是通过组合子问题的解来求解原问题……动态规划算法对每个字问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子问题是都重新计算，避免了这种不必要的计算工作。——《算法导论》
| j\i | 1 | 2 | …… | c |
|---|---|---|---|---|
| 1（底） | ||||
| 2 | ||||
| …… | ||||
| n（顶） | 最终解 |
我们可以用一个如上表格所示二维数组来存储rmax的值，以c为列数，i为行，之后自底向上地求解最大值。动态转移方程为：
这样我们需要c*n的空间。为了减少空间，我们可以将二维数组压缩成一位数组，同样以c为列数，对i~n的物体分别倒序遍历一次这个数组，这样就只需要c的空间了。这样的动态转移方程为：
题目：P1048 采药
完全背包问题
完全背包问题在0-1背包问题的基础上又增加了难度，背包中物品数量没有限制。不过完全背包还是可以用动态规划做，在0-1背包的基础上修改一下就行。
动态转移方程为
题目：P1616 疯狂的采药 这题c*n太大，只能用一维数组做。