询问各算法

fangjiafu

有2n个数，从中选出N个数使其和最接近  2N个数总和的一半

例如
1，2，2，4，6，7  这6个数从中选出3个数使其和等于 （1+2+2+4+6+7）/2


如何和是奇数
1，2，3，4，6，7  就从中选择出3个数使其最接近(1+2+3+6+7)/2  


求这个优化算法！

或者说讨论指点一下也可以！

damcool

先排序A0..An，并求出sum(A0..An)/4，以sum(A0..An)/4为中点，依次取一大于sum(A0..An)/4的某数比如Ak，然后用贪心算法，取出小于sum(A0..An)/4端的两个数值。并令三数的和与sum(A0..An)/4之差的绝对值最小。

edward_35

同问，不知道怎么做

cjaizss

典型的指数级别算法,无法优化.
或者,你就用贪心来近似吧