0-1背包问题：
n个商品（单个商品不可拆分），放入容量为 V 的购物车，如何才能让购物车中的商品总价最大？
书中介绍的动态规划解法是设 dp[i][j] 为前 i 号商品在容量为 j 的购物车中的最大价值，并自底向上求解。这种方法比较紧凑，但是不那么自然，难以想到利用商品编号 i 和容量 j 建立动态规划数组。
下面介绍一种思路较为自然直白的方法：
设 dp[i][j] 为第 i 号~第 j 号商品放入容量 V 的购物车所能产生的最大总价。vdp[i][j] 为 dp[i][j] 对应的商品占用购物车的容量。
则有：
1、dp[i][j] = 0 ; i == j && volume_i > V --- 只有一个商品且放不下
2、dp[i][j] = value_i ; i == j && volume_i <= V --- 只有一个商品且能放下
3、dp[i][j] = 0 ; j - 1 == 1 && volume_i > V && volume_j > V
4、dp[i][j] = value_i + value_j ; j - 1 == 1 && volume_i + volume_j <= V
5、dp[i][j] =value_i ; j - 1 == 1 && volume_i <= V && volume_j > V
6、dp[i][j] =value_j ; j - 1 == 1 && volume_i > V && volume_j <= V
7、dp[i][j] = max(dp[i][k-1] + dp[k+1][j] + 0), i < k < j ; j - 1 > 1 && volume_k > V - (vdp[i][k-1] + vdp[k+1][j])
8、dp[i][j] = max(dp[i][k-1] + dp[k+1][j] + value_k), i < k < j ; j - 1 > 1 && volume_k <= V - (vdp[i][k-1] + vdp[k+1][j])
这些情况看起来很复杂，但是我们可以稍作整理：
dp[i][j] = condition(i, V); i == j
dp[i][j] = value_i + value_j ; j - 1 == 1 && volume_i + volume_j <= V
dp[i][j] = max(condition(i, V), condition(j, V)) ; j - 1 == 1 && volume_i + volume_j > V
dp[i][j] = max(dp[i][k-1] + dp[k+1][j] + condition(k, V - vdp[i][k-1] - vdp[k+1][j]))
其中
condition(k, vRemain) = 0; volume_k > vRemain
condition(k, vRemain) = value_k; volume_k <= vRemain
至此，已找到递归式，可以自底向上求解，代码如下：
测试用例，对于5个商品，放入容量为10的购物车
价值：6 3 5 4 6
体积：2 5 4 2 3
输出最大价值为17，占用体积为9
1 #include "iostream" 2 #include "vector" 3 #include "algorithm" 4 5 #define SIZE 10 6 #define INF 65535 7 8 using namespace std; 9 10 class Goods11 {12 public:13 Goods(int value, int volume)14 {15 this->value = value;16 this->volume = volume;17 }18 public:19 int value;20 int volume;21 };22 23 pair condition(vector &gArr, int k, int vRemain)24 {25 if (gArr.at(k).volume > vRemain)26 {27 return make_pair(0, 0);28 }29 else30 {31 return make_pair(gArr.at(k).value, gArr.at(k).volume);32 }33 }34 35 void package(vector &gArr, int volume)36 {37 int dp[SIZE][SIZE], vdp[SIZE][SIZE];38 int size = gArr.size();39 pair result1, result2;40 41 for (int begin = 0; begin < size; begin++)42 {43 for (int step = 0, i = 0, j = begin; step < size - begin; step++, i++, j++)44 {45 if (i == j)46 {47 result1 = condition(gArr, i, volume);48 dp[i][j] = result1.first;49 vdp[i][j] = result1.second;50 }51 else if (abs(i - j) == 1)52 {53 if (gArr.at(i).volume + gArr.at(j).volume <= volume)54 {55 dp[i][j] = gArr.at(i).value + gArr.at(j).value;56 vdp[i][j] = gArr.at(i).volume + gArr.at(j).volume;57 }58 else59 {60 result1 = condition(gArr, i, volume);61 result2 = condition(gArr, j, volume);62 dp[i][j] = result1.first > result2.first ? result1.first : result2.first;63 vdp[i][j] = (result1.first == 0 && result2.first == 0) ? 0 :64 (result1.first > result2.first ? result1.second : result2.second);65 }66 }67 else68 {69 for (int k = i + 1; k < j; k++)70 {71 result1 = condition(gArr, k, volume - (vdp[i][k - 1] + vdp[k + 1][j]));72 dp[i][j] = dp[i][k - 1] + dp[k + 1][j] + result1.first;73 vdp[i][j] = vdp[i][k - 1] + vdp[k + 1][j] + result1.second;74 }75 }76 }77 }78 79 cout << dp[0][size - 1] << endl;80 cout << vdp[0][size - 1] << endl;81 }82 83 84 void main()85 {86 vector gArr;87 int maxVolume = 10;88 89 gArr.push_back(Goods(6, 2));90 gArr.push_back(Goods(3, 5));91 gArr.push_back(Goods(5, 4));92 gArr.push_back(Goods(4, 2));93 gArr.push_back(Goods(6, 3));94 95 package(gArr, maxVolume);96 }