2.2 0/1背包问题
【题目描述】 0/1背包问题（bag01）
有一个背包，最多能装质量为m的物品，现有n个不同的物品，它们的质量分别是W1,W2,…,Wn，它们的价值分别为C1,C2,…,Cn，求能装入的最大价值。
【输入格式】
第1行为2个整数m和n（1≤m,n≤1 000）。接下来的n行中，每行的2个整数Wi和Ci分别代表第i个物品的质量和价值。
【输出格式】
输出1个整数，即最大总价值。
【输入样例】
8 3
2 3
5 4
5 5
【输出样例】
8
在这道题里，物品要么被装入背包，要么不被装入背包，只有2种选择，因此该问题被称为0/1背包问题。我们可以使用穷举组合、贪心等算法，但是，使用穷举组合算法可能会超时，使用贪心算法不稳定，往往都得不出最优解，因此需要考虑使用动态规划算法。
设f[i][x]表示前i个物品装入承重为x的背包时的最大价值，则状态转移方程如下：
f[i][x]=max{f[i-1][x-W[i]]+C[i],f[i-1][x]}
表示装第i个物品，或不装第i个物品，这两种选择中取最大值。
f[n][m]为最优解，边界条件为f[0][x]=0，f[i][0]=0。
如果读者对上述公式不理解，可以使用表格法来分析。
边界条件f[0][x]=0和f[i][0]=0，分别表示0个物品装入承重为x的背包的最大价值为0，前i个物品装入承重为0的背包的最大价值为0，如表2.1所示。
表2.1
尝试装入第1个物品（W=2，C=3），各个质量段的背包能取得的最大价值如表2.2所示。显然，只要背包的承重大于或等于2，最大价值就都为3。
表2.2
尝试装入第2个物品（W=5，C=4），各个质量段的背包能取得的最大价值如表2.3所示。
表2.3
这是因为第2个物品的质量为5，所以背包的承重为1~4时，最大价值仍为3。当承重大于或等于5时，有2种选择，在2种选择中取最大值即可。
（1） 如果不装入该物品，则当前背包取得的最大价值不变，直接将上一行的值复制下来即可。
（2）如果要装入该物品，则要先将背包腾出5的质量空间。假设背包的承重为x，腾出5的质量空间后：前一部分的质量空间是x−5，用于装前1个物品，这部分的最大价值之前已经求出，即f[1][x−5]；后一部分的质量空间是5，装入该物品的最大价值为4。因此，f[1][5−x]+4为承重为x的背包装入该物品所能取得的最大价值。
所以根据状态转移方程f[i][x]=max{f[i−1][x−W[i]]+C[i]，f[i−1][x]}，有：
f[2][5]=max{f[1][5−5]+4,f[1][5]}
=max{f[1][0]+4,f[1][5]}
=4
f[2][6]=max{f[1][6−5]+4,f[1][6]}
=max{f[1][1]+4,f[1][6]}
=4
f[2][7]=max{f[1][7−5]+4,f[1][7]}
=max{f[1][2]+4,f[1][7]}
=7
f[2][8]=max{f[1][8−5]+4,f[1][8]}
=max{f[1][3]+4,f[1][8]}
=7
依据此法尝试装入第3个物品（W=5，C=5），如表2.4所示。
表2.4
则f[3][8]为最终答案，即最大价值为8。
参考代码如下。
1 //0/1背包问题
2 #include <bits/stdc++.h>
3 using namespace std;
4
5 int w[1001],c[1001],f[1001][1001];
6
7 int main()
8 {
9 int m,n;
10 scanf("%d%d",&m,&n);
11 for(int i=1;i<=n;i++)
12 scanf("%d%d",&w[i],&c[i]);
13 for(int i=1;i<=n; i++) //枚举每个物品
14 for(int j=1;j<=m; j++) //枚举各质量段的背包
15 if(j>=w[i]) //物品i要能装入背包
16 f[i][j]=max(f[i-1][j-w[i]]+c[i],f[i-1][j]);
17 else
18 f[i][j]=f[i-1][j];
19 printf("%d\n",f[n][m]);
20 return 0;
21 }