求一算法!!! — 编程爱好者社区

主题：求一算法!!!

rocky766 [专家分：0] 发布于 2007-02-11 17:07:00

1.给定m个整数,求是否能从这m个整数找出一些整数,使其和等于整数X
2.给定m个整数,求是否能从这m个整数找出n个整数,使其和等于整数X
m,n均给定且数量级较大求一高效算法
最好是DP算法

谢谢~~~~~~~~

沙发

雪光风剑 [专家分：27190] 发布于 2007-02-11 18:42:00

就是背包问题的变形和衍生
看看建模书上的背包问题吧

板凳

wshong [专家分：1880] 发布于 2007-02-12 23:31:00

呵呵。。我也正在解的题目！

3 楼

DataStructureFan [专家分：0] 发布于 2007-02-19 18:00:00

我有一个算法：
先求着Ｍ个数的和Ｓ，将所有数看成一个集合，求这个集合的元素个数在[M/2]以下的所有子集就可以求解，只不过时间复杂度比较大，如果创建一个子集需要１个时间单位的话，那么总共需要2的[M/2]次方个时间单位。时间复杂度较大。

您尚未登录，请登录后再回复。点此登录或注册