0 例题
有n件物品（每种物品都只有一件），w[i]表示物品的重量，v[i]表示物品的价值，现有一个容量为V的背包，应该如何选物品使得书包内装的物品的value之和最大呢？
1 例题分析
约束条件：\(\begin{cases}
\sum_{i=1}^{n}w_ix_i\leq W\\
x_i\in\{0,1\},1\leq i\leq n
\end{cases}
\)
目标函数：\(max\sum_{i=1}^nv_ix_i\)
问题归结于求解满足约束条件，使目标函数达到最大值的解向量X={\(x_1,x_2,x_3,...,x_n\)}。
该问题就是经典的0-1背包问题。要区别于那些用贪心法解决的物品可以切割的背包问题。
2 解题步骤
1. 判断是否能够使用动态规划
假设已经知道X={\(x_1,x_2,x_3,...,x_n\)}是原问题{\(a_1,a_2,a_3,...,a_n\)}的最优解，那么远问题去掉第一个物品就变成了子问题{\(a_2,a_3,...,a_n\)}。子问题的约束条件以及目标函数如下：
约束条件：\(\begin{cases}
\sum_{i=2}^{n}w_ix_i\leq W-w_1x_1\\
x_i\in\{0,1\},2\leq i\leq n
\end{cases}
\)
目标函数：\(max\sum_{i=2}^nv_ix_i\)
则我们只需证明X'={\(x_2,x_3,...,x_n\)}是子问题{\(a_2,a_3,...,a_n\)}的最优解，即证明了最优子结构。
反证法：假设X'={\(x_2,x_3,...,x_n\)}不是子问题{\(a_2,a_3,...,a_n\)}的最优解，则{\(y_2,y_3,...,y_n\)}是子问题的最优解，所以有\(\sum_{i=2}^nv_iy_i>\sum_{i=2}^nv_ix_i\)，且满足约束条件\(\sum_{i=2}^{n}w_iy_i\leq W-w_1x_1\)，我们将约束条件两边同时加上,\(w_1x_1\)，则变为\(w_1x_1+\sum_{i=2}^nw_iy_i\leq W\)，目标函数两边同时加上\(v_1x_1\)，则变为\(v_1x_1+\sum_{i=2}^nv_iy_i>\sum_{i=1}^nv_ix_i\)，说明{\(x_1,y_2,y_3,...,y_n\)}比{\(x_1,x_2,x_3,...,x_n\)}更优，{\(x_1,x_2,x_3,...,x_n\)}不是原问题的最优解，与最初的假设X={\(x_1,x_2,x_3,...,x_n\)}是原问题{\(a_1,a_2,a_3,...,a_n\)}的最优解相悖。问题得证。
2. 构建状态转移方程
每个物品的状态只有两种，就是放入和不放入，分别用1和0表示。\(x_i\)的数值表示第i件的放入和不放入。对于第i件物品的处理状态：
用c[i][j]表示前i件物品放入一个容量为j的背包可以获得的物品的最大价值。
（1）不放入第i件物品，\(x_i=0\)，装入背包的价值不增加，那么问题就转换为“前i件物品放入容量为j的背包中”，最大价值为c[i-1][j]。
（2）放入第i件物品，\(x_i=1\)，装入背包的价值增加\(v_i\)。
那么问题就是转化为“前i-1件物品放入容量为j-w[i]的背包中”，此时能够获得的最大价值就是c[i-1][j-w[i]]+v[i]。
背包容量不足，肯定不能放入；如果能够放入，我们要取放入和不放入的价值最大值。
\(c[i][j]=\begin{cases}
c[i-1][j],j< w_i\\
max\{c[i-1][j],c[i-1][j-w[i]]+v[i]\},j\geq w_i
\end{cases}
\)
3 算法设计
1. 数据结构
一维数组w[i]、v[i]分别记录第i件物品的重量和价值，用二维数组c[i][j]来表示前i件物品放入一个容量为j的背包中可以获得的最大价值。
2. 初始化
将c[i][0]、c[0][j]标记为0，其中i=0,1,...n，j=0,,1,2...,W。
3. 循环阶段
按照状态转移方程求第1个物品的处理情况，得到c[1][j]，其中j=1,2,...W；
按照状态转移方程求第2个物品的处理情况，得到c[2][j]，其中j=1,2,...W；
......
按照状态转移方程求第n个物品的处理情况，得到c[n][j]，其中j=1,2,...W。
4. 构建最优解
c[n][W]就是不超过背包容量能放入物品的最大价值。如何还想知道具体是哪些物品被放入背包，就需要根据c[][]数组逆向构建最优解。首先i=n，j=W，如果c[i][j]>c[i-1][j]，则说明第n件物品被放入了背包，记录这个i值（物品编号），否则就没有；然后令j-=w[n]，i--，直至i=1，循环完毕。
1.4 图解
假设现在有5个物品，每个物品的重量为（2,5,4,2,3），价值为（6,3,5,4,6）。背包容量W=10。如下图：
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| w[] | 2 | 5 | 4 | 2 | 3 |
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| v[] | 6 | 3 | 5 | 4 | 6 |
| 首先，初始化已经预先完成，图中的斜粗体表示当前正在求得状态数值。 |
|||||
| (1) 按照状态转移方程计算第一个物品（i=1）的处理情况，得到c[1][j]，j=1,2,...W。 |
|||||
| c[][] | 0 | 1 | 2 | 3 | 4 |
| --------- | ---------- | --------- | --------- | --------- | --------- |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 6 | 6 | 6 |
| 2 | |||||
| 3 | |||||
| 4 | |||||
| 5 | |||||
| j=1时，\(\because w_1=2>j,\therefore\)c[1][1]=c[0][1]=0; |
|||||
| j=2时，\(\because w_1=2<=j,\therefore\)c[1][2]=max{c[0][2],c[0][0]+6}=6; |
|||||
| j=3时，\(\because w_1=2<=j,\therefore\)c[1][3]=max{c[0][3],c[0][1]+6}=6; |
|||||
| j=4时，\(\because w_1=2<=j,\therefore\)c[1][4]=max{c[0][4],c[0][2]+6}=6; |
|||||
| j=5时，\(\because w_1=2<=j,\therefore\)c[1][5]=max{c[0][5],c[0][3]+6}=6; |
|||||
| j=6时，\(\because w_1=2<=j,\therefore\)c[1][6]=max{c[0][6],c[0][4]+6}=6; |
|||||
| j=7时，\(\because w_1=2<=j,\therefore\)c[1][7]=max{c[0][7],c[0][5]+6}=6; |
|||||
| j=8时，\(\because w_1=2<=j,\therefore\)c[1][8]=max{c[0][8],c[0][6]+6}=6; |
|||||
| j=9时，\(\because w_1=2<=j,\therefore\)c[1][9]=max{c[0][9],c[0][7]+6}=6; |
|||||
| j=10时，\(\because w_1=2<=j,\therefore\)c[1][10]=max{c[0][10],c[0][8]+6}=6; |
|||||
| (2) 按照状态转移方程计算第一个物品（i=2）的处理情况，得到c[2][j]，j=1,2,...W。 |
|||||
| c[][] | 0 | 1 | 2 | 3 | 4 |
| --------- | ---------- | --------- | --------- | --------- | --------- |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 6 | 6 | 6 |
| 2 | 0 | 0 | 6 | 6 | 6 |
| 3 | |||||
| 4 | |||||
| 5 | |||||
| j=1时，\(\because w_2=5>j,\therefore\)c[2][1]=c[1][1]=0; |
|||||
| j=2时，\(\because w_2=5>j,\therefore\)c[2][2]=c[1][2]=6; |
|||||
| j=3时，\(\because w_2=5>j,\therefore\)c[2][3]=c[1][3]=6; |
|||||
| j=4时，\(\because w_2=5>j,\therefore\)c[2][4]=c[1][4]=6; |
|||||
| j=5时，\(\because w_2=5<=j,\therefore\)c[2][5]=max{c[1][5],c[1][0]+3}=6; |
|||||
| j=6时，\(\because w_2=5<=j,\therefore\)c[2][6]=max{c[1][6],c[1][1]+3}=6; |
|||||
| j=7时，\(\because w_2=5<=j,\therefore\)c[2][7]=max{c[1][7],c[1][2]+3}=9; |
|||||
| j=8时，\(\because w_2=5<=j,\therefore\)c[2][8]=max{c[1][8],c[1][3]+3}=9; |
|||||
| j=9时，\(\because w_2=5<=j,\therefore\)c[2][9]=max{c[1][9],c[1][4]+3}=9; |
|||||
| j=10时，\(\because w_2=5<=j,\therefore\)c[2][10]=max{c[1][10],c[1][5]+3}=9; |
|||||
| (3) 按照状态转移方程计算第一个物品（i=3）的处理情况，得到c[3][j]，j=1,2,...W。 |
|||||
| c[][] | 0 | 1 | 2 | 3 | 4 |
| --------- | ---------- | --------- | --------- | --------- | --------- |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 6 | 6 | 6 |
| 2 | 0 | 0 | 6 | 6 | 6 |
| 3 | 0 | 0 | 6 | 6 | 6 |
| 4 | |||||
| 5 | |||||
| j=1时，\(\because w_3=4>j,\therefore\)c[3][1]=c[2][1]=0; |
|||||
| j=2时，\(\because w_3=4>j,\therefore\)c[3][2]=c[2][2]=6; |
|||||
| j=3时，\(\because w_3=4>j,\therefore\)c[3][3]=c[2][3]=6; |
|||||
| j=4时，\(\because w_3=4<=j,\therefore\)c[3][4]=max{c[2][4],c[2][0]+5}=6; |
|||||
| j=5时，\(\because w_3=4<=j,\therefore\)c[3][5]=max{c[2][5],c[2][1]+5}=6; |
|||||
| j=6时，\(\because w_3=4<=j,\therefore\)c[3][6]=max{c[2][6],c[2][2]+5}=11; |
|||||
| j=7时，\(\because w_3=4<=j,\therefore\)c[3][7]=max{c[2][7],c[2][3]+5}=11; |
|||||
| j=8时，\(\because w_3=4<=j,\therefore\)c[3][8]=max{c[2][8],c[2][4]+5}=11; |
|||||
| j=9时，\(\because w_3=4<=j,\therefore\)c[3][9]=max{c[2][9],c[2][5]+5}=11; |
|||||
| j=10时，\(\because w_3=4<=j,\therefore\)c[3][10]=max{c[2][10],c[2][6]+5}=11; |
|||||
| (4) 按照状态转移方程计算第一个物品（i=4）的处理情况，得到c[4][j]，j=1,2,...W。 |
|||||
| c[][] | 0 | 1 | 2 | 3 | 4 |
| --------- | ---------- | --------- | --------- | --------- | --------- |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 6 | 6 | 6 |
| 2 | 0 | 0 | 6 | 6 | 6 |
| 3 | 0 | 0 | 6 | 6 | 6 |
| 4 | 0 | 0 | 6 | 6 | 10 |
| 5 | |||||
| j=1时，\(\because w_4=2>j,\therefore\)c[4][1]=c[3][1]=0; |
|||||
| j=2时，\(\because w_4=2<=j,\therefore\)c[4][2]=max{c[3][2],c[3][0]+4}=6; |
|||||
| j=3时，\(\because w_4=2<=j,\therefore\)c[4][3]=max{c[3][3],c[3][1]+4}=6; |
|||||
| j=4时，\(\because w_4=2<=j,\therefore\)c[4][4]=max{c[3][4],c[3][2]+4}=10; |
|||||
| j=5时，\(\because w_4=2<=j,\therefore\)c[4][5]=max{c[3][5],c[3][3]+4}=10; |
|||||
| j=6时，\(\because w_4=2<=j,\therefore\)c[4][6]=max{c[3][6],c[3][4]+4}=11; |
|||||
| j=7时，\(\because w_4=2<=j,\therefore\)c[4][7]=max{c[3][7],c[3][5]+4}=11; |
|||||
| j=8时，\(\because w_4=2<=j,\therefore\)c[4][8]=max{c[3][8],c[3][6]+4}=15; |
|||||
| j=9时，\(\because w_4=2<=j,\therefore\)c[4][9]=max{c[3][9],c[3][7]+4}=15; |
|||||
| j=10时，\(\because w_4=2<=j,\therefore\)c[4][10]=max{c[3][10],c[3][8]+4}=15; |
|||||
| (5) 按照状态转移方程计算第一个物品（i=5）的处理情况，得到c[5][j]，j=1,2,...W。 |
|||||
| c[][] | 0 | 1 | 2 | 3 | 4 |
| --------- | ---------- | --------- | --------- | --------- | --------- |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 6 | 6 | 6 |
| 2 | 0 | 0 | 6 | 6 | 6 |
| 3 | 0 | 0 | 6 | 6 | 6 |
| 4 | 0 | 0 | 6 | 6 | 10 |
| 5 | 0 | 0 | 6 | 6 | 10 |
| j=1时，\(\because w_5=3>j,\therefore\)c[5][1]=c[4][1]=0; |
|||||
| j=2时，\(\because w_5=3>j,\therefore\)c[5][2]=c[4][2]=6; |
|||||
| j=3时，\(\because w_5=3<=j,\therefore\)c[5][3]=max{c[4][3],c[4][0]+6}=6; |
|||||
| j=4时，\(\because w_5=3<=j,\therefore\)c[5][4]=max{c[4][4],c[4][1]+6}=10; |
|||||
| j=5时，\(\because w_5=3<=j,\therefore\)c[5][5]=max{c[4][5],c[4][2]+6}=12; |
|||||
| j=6时，\(\because w_5=3<=j,\therefore\)c[5][6]=max{c[4][6],c[4][3]+6}=12; |
|||||
| j=7时，\(\because w_5=3<=j,\therefore\)c[5][7]=max{c[4][7],c[4][4]+6}=16; |
|||||
| j=8时，\(\because w_5=3<=j,\therefore\)c[5][8]=max{c[4][8],c[4][5]+6}=16; |
|||||
| j=9时，\(\because w_5=3<=j,\therefore\)c[5][9]=max{c[4][9],c[4][6]+6}=17; |
|||||
| j=10时，\(\because w_5=3<=j,\therefore\)c[5][10]=max{c[4][10],c[4][7]+6}=17; |
4 代码详解
4.1 原始代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define N 10010
int w[N], v[N], c[N][1000];
vector<int> goods;
int main() {
int n, W;
cout << "请输入物品数量和背包容量：";
cin >> n >> W;
cout << "请依次输入每个物品的重量和价值：";
for (int i = 1; i <= n; i++) {
cin >> w[i] >> v[i];
}
for (int i = 0; i <= n; i++) {
c[i][0] = 0;
}
for (int i = 0; i <= W; i++) {
c[0][i] = 0;
}/*初始化*/
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= W; j++) {
if (j < w[i]) {
c[i][j] = c[i - 1][j];
} else {
c[i][j] = max(c[i - 1][j], c[i - 1][j - w[i]] + v[i]);
}
}
}
cout << "装入背包的最大价值为：" << c[n][W] << endl;
int k = W;
for (int i = n; i > 0; i--) {/*逆向构建最优解求哪些物品放入了背包*/
if (c[i][k] > c[i - 1][k]) {
goods.push_back(i);
k -= w[i];
}
}
cout << "分别是哪些物品装入了背包：";
for (vector<int>::iterator i = goods.end() - 1; i >= goods.begin(); i--) {
cout << *i << " ";
}
return 0;
}
4.2 代码优化
1. 空间优化：使c[][]由二维数组变成一维数组
每一次的c[i][j]实际上是由c[i-1][j]和c[i-1][j-w[i]]递推而来，若要保证递推时一维数组化后的c[j-w[i]]保存的是状态c[i-1][j-w[i]]的值，就要求每次主循环中以j=W,W-1,...,1,0的顺序倒推。空间优化后的递推部分代码如下：
for (int i = 1; i <= n; i++) {/*空间优化后的递推部分代码*/
for (int j = W; j > 0; j--) {
if (j >= w[i]) {
c[j] = max(c[j], c[j - w[i]] + v[i]);
}
}
}
2. 范围优化：缩小c[]的更新范围
我们只有在j>=w[i]的情况下才需要更新c[j]的值，所以代码在经过范围优化之后：
for (int i = 1; i <= n; i++) {/*空间优化后-再范围优化的递推部分代码*/
for (int j = W; j > w[i]; j--) {
c[j] = max(c[j], c[j - w[i]] + v[i]);
}
}