背包问题是动态规划中的一个经典题型，其实，也比较容易理解。

当你理解了背包问题的思想，凡是考到这种动态规划，就一定会得很高的分。

背包问题主要分为三种：

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背包问题，其实真没啥难度，记下模板都能过。

上面的讲解应该很详细了，大家多看几遍，应该是可以理解的。

我们下次将讲解完全背包和多重背包问题，我们下次见。