1. 01 背包问题的由来

1.1 01背包问题的特点

一个数学问题：对于 n 个物品有两种选择：放入和不放入背包，而每个物品有一个约束维度，例如每个物品有一个重量；同时又有一个价值维度，我们可以想象为物品的价值。一个合法方案要求·所有物品的重量之和不能超过一个总值（我们可以想象成背包能承受的总重量），求所有方案范围内的 最大价值`。这个问题称为 01背包 问题。

这个问题之所以称为 01 背包，是因为每个物品只有 2 种情况，要么整个放入，要么完全不放入，不能切开一个物品放入一部分，也不能放入多次（放入多次的背包算法要做一些调整，本题不作讨论）。我们过去学过一条题叫 小数背包 ，那条题就是可以放入一部分的，我们可以用贪心算法来解决那个问题，但是，针对 01 背包问题，贪心算法是无能为力的。

1.2. 01枚举和01背包问题

01枚举 算法是可以用来解决一部分 01背包 问题的，每一个方案对应成一个二进制数，如果有 n 个物品，方案的解空间是 [0,$2^{n+1}$-1] 。当 n 比较大的时候，枚举的范围就很大，就会超时。一般来说， n 不超过 20 的时候可以用 01枚举 算法，$2^{21}$ -1 ，大约是 2000000。如果 n 大于 20，就要用别的算法来优化了。 n = 20 是一个分水岭，这是一个解题经验。

2. 为什么贪心算法不适用于 01 背包问题

有些同学会不服气，觉得用贪心算法可以解决这个问题。下面用样例数据来说明为什么不可以。

贪心算法，就是通过局部最优解来追求全局最优解，局部最优解自然就是按照物品的性价比来排序了，每个物品的价值/物品重量，可以看作是性价比。往背包里面选择物品的过程就是先选性价比高的，再选性价比低的，直到放不下为止。

例如，有 3 个物品，背包容量为 10 。下面的数据第一行是物品的重量，第二行是物品的价值：

5 6 5
10 18 11  

上面数据中，性价比最高的是第二个物品，有 $p_2$/$w_2$ = 3 ，第 1 个物品性价比是 2 ，第 3 个物品是比 2.2。所以，如果按照贪心算法的思维，那就是首先选第 2 个物品，之后就放不下第别的物品了（因为背包容量为 10 ），这个方案的总价值为 18 。

正确的最有方案是 选第 1 和第 3 个物品，总价值为 21。

我们回过头去看，可以发现，有一些性价比高的物品放入了之后，就无法放入其它性价比偏低的物品，但是这个方案可能是一个剩余空间比较大的方案，没有充分利用起背包的效能，从而出现了 捡了籽麻，丢了西瓜 的结果，这些性价比高的物品可能是一个陷阱。

当 n 很多的时候，你说不清哪一个物品是陷阱，可能性价比最高的物品是陷阱，也可能是性价比第 7 的物品是陷阱。我们用贪心算法是思维很难跳过这些陷阱。

3. 用动态规划算法解决 01 背包问题

我们定义一个状态： dp[i][j] ，它保存的数据为 考虑了从第 1 到第 i 个物品之后，对于空间（或者重量，反正就是那个约数维度） 为 j 的背包，可以放入物品的最大价值。

注意，上面说的一个关键信息是：考虑了从第 1 到第 i 个物品后，这些物品不需要预先排序，我们先考虑第 1 个物品得出 dp[1][j]； 然后第 2 阶段是在 dp[1][j] 的基础上考虑第 1 和第 2 个物品，推出 dp[2][j]，然后再来第 3 阶段.....每一个阶段 i ，都是基于 1 到 i-1 个物品的状态已知的情况下，去推算 1 到 i 物品的状态。

接下来，我们就要考虑（推算）如何从 i-1 状态，去推算出 i 状态。

对于第 i 个物品，无非就是放入和不放入两种可能，dp[i][j] 所定义的是：第 1 到 第 i 个物品的范围内，对于空间（或者重量）为 j 背包能装入的价值最大值，在此之前，我们已经算出了 dp[i-1]，如果要放入第 i 个物品，那么就要从 j 空间中腾出 $w_i$ 出来方它，而 j-$w_i$ 用于放入 1 到 i-1 那些物品，所以，对于放入 i 物品的价值是： dp[i-1][j-$w_i$] + $p_i$ ； 而如果不放入 i 物品，那么空间 j 全部用来放 1 到 i-1 物品，它的价值可以是 dp[i-1][j]。

所以，状态转移方程是dp[i][j] = max(dp[i-1][j-$w_i$]+$p_i$, dp[i-1][j])

4. 推演举例

4 9
2 3 4 5
3 4 5 7

上面数据的意思是，有 4 个物品，背包的容量为 9 。然后第二行和第三行分别是 4 个物品的体积和价值。

1. 第一步，我们画出一个表格。表格的横坐标表示背包空间，纵坐标表示第几轮的推演，中间的区域是我们即将要填入的数字。（在程序里面，其实就是定义二维数组 dp[n+1][c+1] ）

2. 一开始，如果是没有任何物品的放入， dp[0][j] 为 0 。这是递推的起点。（这个步骤在程序里面就是数组的初始值，如果是用全局变量，默认值就是 0 )

3. i = 1 , 枚举 j = 0 到 v , dp[1][j] = max(dp[0][j-$w_1$]+$p_1$, dp[0][j]) ，填入表格。下图中，红框位置为最放入了第 1 个物品的情况，红框前的格子为没放入第 1 个物品的情况。

3. i = 2 , 枚举 j = 0 到 v , dp[2][j] = max(dp[1][j-$w_2$]+$p_2$, dp[1][j]) ，填入表格。下图中，红框位置为最放入了第 2 个物品的情况，红框前的格子为没放入第 2 个物品的情况。

4. i = 3

5. i = 4

6. 结论

第 4 行，第 9 列的数字（dp[i][v]） 就是容量为 9 ，考虑了全部物品（第 1 到第 4 个）之后，可以实现的最大价值。

5. 例题

题目描述

给定一个容量为 C 的背包， n 个体积分别为 $w_1$ , $w_2$ , ... , $w_n$ ​的物品，物品 i 放入背包能产生 $p_i$ ​的价值 ( i = 1 , 2 , ... , n , $p_i$ > 0 , $w_i$ > 0)。

每个物品要么整个放入背包，要么不放。放入物品的总体积不能超过背包的总容量 C 。

要求找出最大价值的装包方案。

输入格式

第一行包含两个正整数 n 和 C ( 1 ≤ n ≤ 100 , 1 <= C <= 30000 )

第二行含 n 个正整数 $w_i$ 分别表示 n 个物品的体积 ( 1 <= $w_i$ <= C )。

第三行含 n 个正整数 $p_i$ 分别表示 n 个物品放入背包能产生的价值( 1 <= $p_i$ <= 1000 )。

输出格式

一个整数，代表最大价值。

样例

4 9
2 3 4 5
3 4 5 7

12

程序填空

#include<bits/stdc++.h>
using namespace std;
int dp[填空(1)][填空(2)];
int w[101],p[101];
int main()
{
	int n,c,i,j;
	
	scanf("%d%d",&n,&c);
	
	for(i=1;i<=n;i++)
		scanf("%d",&w[i]);

	for(i=1;i<=n;i++)
		scanf("%d",&p[i]);

	for(i=1;i<=n;i++)
	{
		for(j=0;j<w[i];j++) //这一部分空间很小，不可能放入第 i 个物品
			dp[i][j] = 填空(3);
		
		for(j=w[i];j<=c;j++)
			dp[i][j] = max( 填空(4) , dp[i-1][j]);		 
	}
	
	cout<<填空(5);

	return 0;
}

填空(1): {{ input(1) }}

填空(2): {{ input(2) }}

填空(3): {{ input(3) }}

填空(4): {{ input(4) }}

填空(5): {{ input(5) }}