PIGWORLD

学无止境

背包问题 -- 1) 思路,递归求解

        最近看了《算法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)的最大值也就完称了我们的任务了。
        下面的程序代码是按以上的思路编写的:
 http://pigworld.blogbus.com/files/1134918024.jpg
我么定义了一个类型为Item的N项数组,对于每一个可能的项,我们递归的计算所能得到的最大值,然后挑出那些值中的最大项返回。
        需要说明的是,上面的代码不应该成为正式的代码,如果按上面的代码画出每次函数调用的二叉树图,就会发现有大量重复的计算来处理同一个问题,其结果就是耗费指数级的时间,因而是低效的。
        下一篇背包问题 -- 2) 改进,自顶向下的动态编程将会介绍如何对上面的代码改进,使耗费的时间从指数级减少到线性级。

posted on 2006-01-03 23:15 PIGWORLD 阅读(8177) 评论(5)  编辑 收藏 引用

Feedback

# re: 背包问题 -- 1) 思路,递归求解 2006-04-24 13:51 dimensioll

这样会重复取同一个价值大的问题。错误  回复  更多评论   

# re: 背包问题 -- 1) 思路,递归求解 2006-05-14 10:54 SIMMONM

算法没错,不会重复取同一个价值大的问题  回复  更多评论   

# re: 背包问题 -- 1) 思路,递归求解 2009-04-24 11:43 klein

space 那 >=  回复  更多评论   

# re: 背包问题 -- 1) 思路,递归求解 2012-07-24 16:05 hello

@klein
算法看起来没有问题,但是求解的结果的确有问题。 能仔细找找吗?  回复  更多评论   

# re: 背包问题 -- 1) 思路,递归求解 2012-07-24 16:06 hello

@hello
这样修改后就ok了:
(space = cap - fruits[i].getSize()) >= 0

谢谢  回复  更多评论   



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理