背包问题是动态规划中的一个经典题型，其实，也比较容易理解。
当你理解了背包问题的思想，凡是考到这种动态规划，就一定会得很高的分。
背包问题主要分为三种：
01背包 完全背包 多重背包
其中，01背包是最基础的，最简单的，也是最重要的。
因为其他两个背包都是由01背包演变而来的。所以，学好01背包，对接下来的学习很有帮助。
废话不多说，我们来看01背包。
01 背包问题：给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。
问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
第一眼看上去，我们会想到贪心（背包问题还不会QAQ）。
用贪心算法来看，流程是这样的：
1.排序，按价值从大到小排序
2.选价值尽可能大的物品放入。
但是，贪心做这题是错的。
让我们举个反例：
n=5,C=10
重量 价值
第一个物品： 10 5
第二个物品： 1 4
第三个物品： 2 3
第四个物品： 3 2
第五个物品： 4 1
用贪心一算。答案是5，但正解是用最后4个，价值总和是10.
那将重量排序呢？
其实也不行。
稍微一想就想到了反例。
我们需要借助别的算法。
贪心法用的是一层循环，而数据不保证在一层循环中得解，于是，我们要采用二层循环。
这也是背包的思想之一。
来看背包算法：
1.用二维数组dp 【 i 】 【 j 】，表示在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值
比如说上面的那个反例：
dp 【 1 】 【 3 】 = 4 + 3 = 7.
2.01背包之所以叫“01”，就是一个物品只能拿一次，或者不拿。
那我们就分别来讨论拿还是不拿。
（1）j < w【i】 的情况，这时候背包容量不足以放下第 i 件物品，只能选择不拿
dp 【 i 】 【 j 】 = dp 【 i - 1 】 【 j 】；
（2）j>=w【i】 的情况，这时背包容量可以放下第 i 件物品，我们就要考虑拿这件物品是否能获取更大的价值。
~如果拿取，dp 【 i 】 【 j 】 = dp 【 i - 1 】 【 j - w 【 i 】 】 + v 【 i 】。 这里的dp 【 i - 1 】 【 j - w 【 i 】 】指的就是考虑了i-1件物品，背包容量为 j-w【i】 时的最大价值，也是相当于为第i件物品腾出了w【i】的空间。
~如果不拿，dp 【 i 】 【 j 】 = dp 【 i-1 】 【 j 】
到底拿不拿呢？要看拿与不拿那个结果更大了。
看，这用到了动态规划的思想：在求值时会用到之前状态的结果。
我们就可以得出状态转移方程了。
1 if(j>=w【i】)
2 dp【i】【j】=max(dp【i-1】【j】,dp【i-1】【j-w【i】】+v【i】);
3 else
4 dp【i】【j】 = dp【i-1】【j】;
于是，完整代码就出来了：
code：
1 int n,c,w【1001】,v【1001】;
2 int dp【1001】【1001】;
3 cin]n]c;
4 for(int i=1;i<=n;i++)
5 cin]w【i】]v【i】;
6 for(int i=1;i<=n;i++) //物品
7 {
8 for(int j=1;j<=c;j++) //从一枚举到C
9 {
10 if(j>=w【i】)
11 dp【i】【j】=max(dp【i-1】【j】,dp【i-1】【j-w【i】】+v【i】); //最大值
12 else
13 dp【i】【j】=dp【i-1】【j】;
14 }
15 }
16 cout[dp【n】【c】[endl;//n个物品，背包空间为c的dp值
那么，这是二维的01背包，可以看出，数组受空间限制，不能开太大，所以，我们还有一种优化01背包，只有一维的数组
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组dp【 i 】 【 0..V 】的所有值。那么，如果只用一个数组dp 【 0..V 】，能不能保证第i次循环结束后dp【 v 】中表示的就是我们定义的状态dp 【 i 】 【 v 】呢？dp【 i 】【 v 】是由dp【 i-1 】【 v 】和dp【 i-1 】【 v-c【i】 】两个子问题递推而来，能否保证在推dp【 i 】【 v 】时（也即在第i次主循环中推dp【 v 】时）能够得到dp【 i-1 】【 v 】和dp【 i-1 】【 v-c【i】 】的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推dp【 v 】，这样才能保证推dp【 v 】时dp【 v-c【i】 】保存的是状态dp【 i-1 】【 v-c【i】 】的值。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了dp【 i 】【 v 】由dp【 i 】【 v-c【 i 】 】推知，与本题意不符，但它却是完全背包最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。
1 for(int i=1;i<=n;i++)
2 {
3 for(int v=c;v>=0;v--)
4 {
5 dp【v】=max(dp【v】,dp【v-c【i】】+w【i】);
6 }//代码效果参考：http://www.ezhiqi.com/zx/art_3562.html
7 }//代码效果参考：http://www.ezhiqi.com/zx/art_6850.html
这就是代码，相比上面的简洁了许多，既优化了空间，又减少了代码长度。
这就是01背包问题，其实真没啥难度，记下模板都能过。
上面的讲解应该很详细了，大家多看几遍，应该是可以理解的。
我们下次将讲解完全背包和多重背包问题，我们下次见。
