|
|
发表于 2012-9-22 23:32:19
|
显示全部楼层
本帖最后由 古明地觉 于 2012-9-22 10:35 编辑
赛事名称 SubsetSum挑战赛
赛事时间 2013年12月里和国际赛不冲突的连续3天。
赛事项目 SubsetSum@home
赛事规则 按照boincstats中的数据统计结果
赛事理由 该项目可以运行在Android平台上，Tegra 3测试表明运算速度和I7 2630QM 相差不大。任务本身计算量并不算大，得分率也是比较不错的。因此可以借此在Android平台上推广Boinc项目。最佳设备是Android平板，其次是手机。（没必要提续航问题。笔记本也是能带出去的，笔记本也是能计算的。。。平板也是要带出去的，但是平板也可以放在家里充电。手机也一样。仅仅是为了推广Android平台上的boinc计算，并不需要一定使用Android平台计算。大家如果有Android平台的设备吧，可以在闲置的时候也让其参与到计算中。）
扩展内容 子集合加总问题(Subset sum problem)是计算复杂度理论和密码学中一个很重要的问题。问题可以描述为：给一个整数集合，问是否存在某个非空子集，使得子集内中的数字和为0？例：给定集合{−7, −3, −2, 5, 8}，答案是YES，因为子集{−3, −2, 5}的数字和是0。这个问题是NP完全问题，且或许是最容易描述的NP完全问题。
一个等价的问题是：给一个整数集合和另一个整数s，问是否存在某个非空子集，使得子集中的数字和为s？子集合加总问题可以想成是背包问题的一个特例。
动态规划解法
用动态规划的方法，能够以伪多项式时间解决子集合加总问题。我们假定输入序列为：
x1, ..., xn
我们需要判断是否存在某个非空子集，使得子集中的数字和为0。我们序列中负数的和为N，正数的和为P。定义函数Q(i, s)，它的涵义为:
是否存在x1, ..., xi的非空子集，使得子集中的数字和为s
子集合加总问题的答案即为Q(n, 0)。
显然，如果s < N或者s > P，则Q(i,s) = false，因此无需记录这些值。我们把Q(i, s)的值保存在数组中，其中1 ≤ i ≤ n且N ≤ s ≤ P。
接下来使用循环来填充数组。首先，对于N ≤ s ≤ P，设定
Q(1, s) := (x1 = s)
随后，对于i = 2, …, n和N ≤ s ≤ P，设定
Q(i, s) := Q(i - 1, s) 或 (xi = s) 或 Q(i - 1, s - xi)
算法运行的总时间为O(n(P - N))。
对算法加以改动，即可返回和为0的子集。
在计算复杂度理论中，这种解法需要的时间并不算多项式时间，这是因为P - N同输入大小并不成线性关系。原因在于输入大小仅仅取决于表达输入所需要的比特数。算法的时间复杂度同N与P的值成线性关系，而它们的值与表达它们所需的比特数成幂关系。
转自维基百科 |
评分
-
查看全部评分
|
发表于 2012-7-25 03:45:27
发表于 2012-9-8 16:05:42
发表于 2013-4-5 18:13:30