s******e
发帖数: 108 | 1 give array of 2*n integers A,
partition it into two array of n element(A1,A2),
make their sum closest to each other(min | sum A1 - sum A2 | ) | w****x
发帖数: 2483 | 2 一种方法是看所有的n subset.
一种方法是先随便分成两个n的sub array, 然后再while循环里试图交换两个element以
使得| sum A1 - sum A2 | 小余当前最优解, 终止条件是找不到这样的swap | t*****l
发帖数: 241 | 3 np hard problem.
【在 s******e 的大作中提到】
: give array of 2*n integers A,
: partition it into two array of n element(A1,A2),
: make their sum closest to each other(min | sum A1 - sum A2 | )
| f*****e
发帖数: 2992 | 4 http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
【在 s******e 的大作中提到】
: give array of 2*n integers A,
: partition it into two array of n element(A1,A2),
: make their sum closest to each other(min | sum A1 - sum A2 | )
| f*****e
发帖数: 2992 | 5 刚才推了一下，转化为最大割问题，我们知道最大流最小割是P，最大割只有MIT Goema
ns的随机近似算法，这个问题比Goemans的多两个条件。
【在 f*****e 的大作中提到】
: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=ri
| t******t
发帖数: 21 | 6 how about greedy?
sort the array say {1,2,3, 80, 85, 99, 100, 1000}
pick 1000 first in A1
pick 100 in A2
if (sum1 -sum2)900 > next max 99
pick next min 1 in A1 and next max 99 in A2
else if sum1 > sum2 pick next max in A2, then repeat recursively
【在 s******e 的大作中提到】
: give array of 2*n integers A,
: partition it into two array of n element(A1,A2),
: make their sum closest to each other(min | sum A1 - sum A2 | )
|
|
