2007-12-29

[原创]这个题目有点难

关键字: 组合
这个论坛牛人比较多哈，请教一个算法题：

有A、B两个集合（元素为整数，可重复出现），其中A中若干整数的代数和与B中若干整数的代数和相等，用算法求出所有可能的组合，并指出在哪种组合方式下用到A和B中的整数最多（每个数只能用一次）。

能用函数式实现更好啦，让俺也学习学习。：）

为了更好的理解题目含义，举个例子吧。

A: 1 3 5 6
B: 2 4 7 9

组合1: 1+6=7 共用到3个数
组合2: 1+3=4, 6=2+4 共用到6个数
组合3: 1+5=2+4, 3+6=9 共用到7个数
......

在列出的组合方式中，组合3用到的数最多。
评论
Elminster 2008-04-28
这个问题叫做“子集和问题”（subset sum problem），算是经典问题了，一般的描述方式是这样的：给你一个数的集合，问你其中是否存在一个子集，这个子集中的元素之和为 0。把你的问题中的 B 中所有元素取负，然后与 A 合并，就可以转化为这个标准描述了。

这个问题，现在几乎可以肯定不存在有效的一般算法 —— CSDN 上这个解法不靠谱。具体怎么解这个问题，取决于你的输入数据的两个特征：1. 集合的大小。2. 集合中元素的取值范围。如果集合比较小、取值范围比较大，一般就是直接搜索可能的集合；反过来，如果集合比较大、取值范围比较小，有一个动态规划的算法可以用（和最长公共子串是有一点相似）。具体算法上英文维基看吧，我懒得写了。
songyangaaron 2008-04-25
高手呢？？？

转一个CSDN的解法吧，刺激一下


引用 2 楼 lokienigma 的回复:
分析：第一我们只需要一个等式就可以了。
像上面组合三：
其实等价于一个：1+5+3+6 = 2+4+9.
也就是这个等式能取到最多个数。
然后这个用数学里的级数方法求等式：

(1+x^k1)(1+x^k2)......(1+x^kn)

和
（1+y^l1)(1+y^l2)........(1+y^lm)
中次数相同的元素，然后取最大的的组合。

呵呵，这个是通用而简单的数学思路。

这个题目似乎并没有技巧型的方法，还是靠枚举的方法，就是看哪种的数据…
songyangaaron 2008-04-23
好长时间没来了，楼上的算法行得通吗？
sunnycare 2008-02-13
google 最长公共子序列 。。。
先排序两个集合，然后仿照最长公共子序列的算法，设计你的程序。

所要改造的类似于java中改写equals方法
songyangaaron 2008-01-03
莫非是题目太简单了大家都看不上眼？第一步是很简单，关键第二步哪位有比较好的处理方式吗，不会还是穷举吧？
发表评论

提醒: 该博客已发表在公共论坛，博客所有留言会成为论坛回贴，留言请注意遵守论坛发贴规则

您还没有登录，请登录后发表评论

songyangaaron
搜索本博客
博客分类
最近加入圈子
最新评论