c********d
发帖数: 173 | 1 如果给定一个长度为2n的整数数组，要从中选出n个元素，使得它们的和和余下的n个元
素的和最接近
这个问题的算法是什么？谁能给出c++/java程序？ | P***P
发帖数: 1387 | 2 先求总和 = x, 然后找n个元素使其和约为x/2, 剩下的就是Knapsack problem了
当然这个肯定不是最优的 | i**********e
发帖数: 1145 | 3 这问题不简单，应该是 dp，这里有一个类似的解法，不过两个subset S1 和 S2 不局
限于拥有同样 n 个元素。
See "Balanced Partition" here:
http://people.csail.mit.edu/bdean/6.046/dp/ | i*******6
发帖数: 107 | 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<上次的10， N=N-t=0， 交换7和3
结束
结果
11,2,7,4,4
5,3,9,10,1
时间复杂度：
最坏情况O(n^2)，如果能改进找差值的算法，可以做到nlogn | i*******6
发帖数: 107 | 5 又想了下，找差值可以考虑这样搞
1,2,3,4,4
|
pointer1
5,7,9,10,11
|
pointer2
两个都指向当前最后一个数
这样如果两个差大于N,那么减pointer2,否则减pointer1.
交换过的就不再考虑了（因为排过序，可以保证每次都是最优解）
不过这样也是O(n^2)
再想想... | r*******n
发帖数: 266 | 6 你看就是POMDP做多了..不是啥问题人家都认approximation的...
【在 P***P 的大作中提到】
: 先求总和 = x, 然后找n个元素使其和约为x/2, 剩下的就是Knapsack problem了
: 当然这个肯定不是最优的
| t*********7
发帖数: 255 | | g**********y
发帖数: 14569 | 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**********e
发帖数: 1145 | 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;
| h**********l
发帖数: 6342 | 10 sort
然后取头n/2和尾n/2
【在 c********d 的大作中提到】
: 如果给定一个长度为2n的整数数组，要从中选出n个元素，使得它们的和和余下的n个元
: 素的和最接近
: 这个问题的算法是什么？谁能给出c++/java程序？
| g**********y
发帖数: 14569 | 11 USACO的题是1~N的数字，换成int[] a也差不多。
就是把和/2， 就是目标值。然后用DP计算可以到达x的办法总数，存在dp[]里。
计算的时候，倒序计算，就不需要额外空间。
最后dp[sum/2]就是办法总数，因为对称性，所以除2.
【在 i**********e 的大作中提到】
: 可以说说思路吗？
| P***P
发帖数: 1387 | 12 同行啊, 握手握手...
【在 r*******n 的大作中提到】
: 你看就是POMDP做多了..不是啥问题人家都认approximation的...
|
|
