subset sum的问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

subset sum的问题

subset sum的问题# JobHunting - 待字闺中

c*d2012-02-14 08:02

1 楼

如果给定一个长度为2n的整数数组，要从中选出n个元素，使得它们的和和余下的n个元
素的和最接近
这个问题的算法是什么？谁能给出c++/java程序？

P*P2012-02-14 08:02

2 楼

先求总和 = x, 然后找n个元素使其和约为x/2, 剩下的就是Knapsack problem了
当然这个肯定不是最优的

i*e2012-02-14 08:02

3 楼

这问题不简单，应该是 dp，这里有一个类似的解法，不过两个subset S1 和 S2 不局
限于拥有同样 n 个元素。
See "Balanced Partition" here:
http://people.csail.mit.edu/bdean/6.046/dp/

i*62012-02-14 08:02

4 楼

Greedy Algorithm:
排序，然后分两半，计算值差/2 = N
两个指针找绝对值最接近N的两个数，记录差t，要求t不大于上次查找的t
直到N=0或者没有这样的t存在
比如
11,5,4,7,4,2,9,3,10,1
先排序：
1,2,3,4,4,5,7,9,10,11
分成
1,2,3,4,4
5,7,9,10,11
计算差
N=28/2 = 14
第一次
找到11和1，差t=10, N=N-t=4，交换11和1
第二次
找到7和3，差t=4结束
结果
11,2,7,4,4
5,3,9,10,1
时间复杂度：
最坏情况O(n^2)，如果能改进找差值的算法，可以做到nlogn

i*62012-02-14 08:02

5 楼

又想了下，找差值可以考虑这样搞
1,2,3,4,4
|
pointer1
5,7,9,10,11
|
pointer2
两个都指向当前最后一个数
这样如果两个差大于N,那么减pointer2,否则减pointer1.
交换过的就不再考虑了（因为排过序，可以保证每次都是最优解）
不过这样也是O(n^2)
再想想...

r*n2012-02-14 08:02

6 楼

你看就是POMDP做多了..不是啥问题人家都认approximation的...

【在 P***P 的大作中提到】

: 先求总和 = x, 然后找n个元素使其和约为x/2, 剩下的就是Knapsack problem了
: 当然这个肯定不是最优的

t*72012-02-14 08:02

7 楼

背包问题

g*y2012-02-14 08:02

8 楼

这个是对USACO的解答，你的问题改一下就行
private long solve(int N) {
if (N*(N+1)%4 != 0) {
return 0;
}

int M = N*(N+1)/4;

long[] dp = new long[M+1];
dp[0] = 1;

for (int i=1; i<=N; i++) {
for (int j=M-i; j>=0; j--) {
dp[j + i] += dp[j];
}
}

return dp[M]/2;
}

i*e2012-02-14 08:02

9 楼

可以说说思路吗？

【在 g**********y 的大作中提到】

: 这个是对USACO的解答，你的问题改一下就行
: private long solve(int N) {
: if (N*(N+1)%4 != 0) {
: return 0;
: }
:
: int M = N*(N+1)/4;
:
: long[] dp = new long[M+1];
: dp[0] = 1;