关于subsetsum@ home的几点疑问

gameboybf2142

看了一下subsetsum@home项目主页，有几点疑问

subsetsum问题：
子集和问题 给定一个n个整数的集合X = {x1, x2, …, xn}和整数Y，找出和等于Y的X的子集subX。 比如说，如果X ={10,20,30,40,50,60} 和 Y = 60 则有三种不同长度的解，它们分别是 subY = {10，20，30}，{20，40} 和{60}

这个项目貌似是要验证一个假设：
集合X（元素都是正整数）最大的元素为m，元素个数为n，元素之和为S。如果 n>[m/2]+1，那么对于任何符合 m<t<S-m 的整数 t 必有一个X的子集使该子集元素的和为t

PS：[a]表示不超过a的最大整数

而项目的过程就是不断随机生成集合来检测符不符合假设


项目的源代码地址：https://github.com/travisdesell/Subset-Sum

问题1：这个项目用的是什么算法来验证假设的？ 一般来说，这个问题的算法应该是动态规划，不过我看了源码之后发现貌似还要生成杨辉三角，不知道有什么用？

问题2：在项目的网站上可以看到一些验证的结果，但是其中有不满足假设的结果，那么假设就应该被推翻了，为什么项目还要继续？

gameboybf2142

怎么没人回我。。。。。。求解答，求讨论啊。。。。。。。。。。。。。。。。

894606908

大神们还未睡醒？

xx318088

等fwjmath来吧他应该懂一些

gameboybf2142

我算了半天的subsetsum, 看了一下网站，果断退出。。。。。。

话说有一道信息学竞赛题就考了subsetsum问题。。。。。

xuyongchen

问题1：算法我不懂。。还是等fm来吧
问题2：这个项目的目的是不是为了确定一定能够找出满足条件的解？也就是说有解就可以。。。

总之还是等fm来解释一下吧

gameboybf2142

回复 6# xuyongchen
问题2：这个项目是证明一个假设。那么既然有反例，就说明假设不成立了。

gameboybf2142

话说我是不是发错地方了。。。。。。。。。。。

fwjmath

我看了代码，核心部分的确是动态规划。要用到二项式是因为这个项目是检查所有可能的子集，为了生成所有的子集就必须计算二项式。

另外，网站上现在还没有找到反例。那些例子（我没有仔细检查），貌似都是符合原来的假设的。项目方表示，那些接近边沿的例子非常有趣，可能可以在其中找到规律。

再另外，貌似项目方正在开发CUDA的计算程序。

gameboybf2142

回复 9# fwjmath
哦，不好意思，我看错了，那些failed sets都是不符合n>[m/2]+1的