首页 > 编程语言 > 详细

算法二之子集和数问题

时间:2015-07-12 22:53:44      阅读:252      评论:0      收藏:0      [点我收藏+]

什么是子集和数问题?

问题分析,简单的说就是有n 个数在这N个数中选取若干个数使得这几个数的和为M。

解决问题的途径;使用回溯法。

最后形成二叉树

技术分享

左边是有这个数,右儿子是没有这个数。

使用回溯法,一个一个的进行计算,时间太长。

使用一定的条件,使得时间减短。

前提是对所有的数字进行非降序排序,然后在进行下面的操作。

限界函数,将有可能产生解的集合进行缩小。有的不可能产生可行解的直接进行排除。

∑W(i)X(i)+∑W(i)>=M

∑W(i)X(i)+W(k+1)>M

如果加入一个数k,如果k-1个数的和小于M,加上K小于M但是加上k的下一个数后大于M,那么数k也不用进行计算,直接排除。

算法二之子集和数问题

原文:http://www.cnblogs.com/ysugyl/p/4641573.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!