最近看了《算法I－IV（C++语言描述）》中关于动态编程求解背包问题的部分，感觉书中描述的不是很详细，在这里通过我个人的理解再加上书中的描述，再重温下这一经典问题的动态编程求解方法。
所谓的背包问题，可以描述如下：一个小偷打劫一个保险箱，发现柜子里有N类不同大小与价值的物品，但小偷只有一个容积为M的背包来装东西，背包问题就是要找出一个小偷选择所偷物品的组合，以使偷走的物品总价值最大。我们可以定义以下结构：
struct Item {
int size; //保存物品大小
int val; //保存物品价值
};
例如有下表中的物品：
|
Index |
0 |
1 |
2 |
3 |
4 |
|
Item |
A |
B |
C |
D |
E |
|
Size |
3 |
4 |
7 |
8 |
9 |
|
Val |
4 |
5 |
10 |
11 |
13 |
上表中第一行（Index）是物品在程序中的索引号，第二行（Item）是物品的标示，第三行（Size）是物品的大小，第四行（Val）是物品的价值，而每一列又对应了一类物品。假设小偷背包的容积为17，则小偷能够拿走5个A价值为20的物品，或者1个D和1个E，价值为24的物品，等等。
为了使小偷在背包容积为cap的情况下，能够偷走最大价值的物品，我们可以假设小偷足够聪明，无论背包容积cap为多少，小偷总能找到最优的组合使背包中所装物品的价值最大。
倘若我们定义函数：
int knap( int cap );
该函数的返回值为容积为cap的背包所装物品的最大价值。对于cap为17的背包，因为有5类物品，所以所装物品的价值有以下组合：
1） 4 + knap( 17 - 3 )，即 item[0].val + knap(cap - item[0].size);
2) 5 + knap( 17 - 4 )，即 item[1].val + knap(cap - item[1].size);
3) 10 + knap( 17 - 7 )，即 item[2].val + knap(cap - item[2].size);
4) 11 + knap( 17 - 8 )，即 item[3].val + knap(cap - item[3].size);
5) 13 + knap( 17 - 9 )，即 item[4].val + knap(cap - item[4].size);
因为小偷已经帮助我们找到了cap = cap - item[i].size的最优组合，所以我们只需要找到item[i].val + knap(cap - item[i].size)的最大值也就完称了我们的任务了。
下面的程序代码是按以上的思路编写的：
我么定义了一个类型为Item的N项数组，对于每一个可能的项，我们递归的计算所能得到的最大值，然后挑出那些值中的最大项返回。
需要说明的是，上面的代码不应该成为正式的代码，如果按上面的代码画出每次函数调用的二叉树图，就会发现有大量重复的计算来处理同一个问题，其结果就是耗费指数级的时间，因而是低效的。