最近看了《算法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项数组,对于每一个可能的项,我们递归的计算所能得到的最大值,然后挑出那些值中的最大项返回。
需要说明的是,上面的代码不应该成为正式的代码,如果按上面的代码画出每次函数调用的二叉树图,就会发现有大量重复的计算来处理同一个问题,其结果就是耗费指数级的时间,因而是低效的。