背包问题是动态规划中的一个经典题型，其实，也比较容易理解。
当你理解了背包问题的思想，凡是考到这种动态规划，就一定会得很高的分。
背包问题主要分为三种：
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 } 7 }
这就是代码，相比上面的简洁了许多，既优化了空间，又减少了代码长度。
这就是01背包问题，其实真没啥难度，记下模板都能过。
上面的讲解应该很详细了，大家多看几遍，应该是可以理解的。
我们下次将讲解完全背包和多重背包问题，我们下次见。
