小弟不才，刚学习C语言，被一道题目给难住了，请高手给说下思路即可，问题如下：
任意2n个整数，从中筛选出n个数，使它们的和最接近这2n个数总和的二分之一。

为了大家理解方便，假定n=250吧，也就是数组内一共有500个元素，元素数值是任意的。

[ 本帖最后由 thuining 于 2012-7-11 10:39 编辑 ]

我又想暴力求解了。

昨晚想了半晚上，有一个思路但我感觉不是最优的，因为第三步我觉得m=m-0.5也是可行的，只是不知道到底哪一种方案更接近问题求解
1、首先求这2n个数的均值m（不是整数的话取整）
2、从第一个数开始，遍历寻找数组中另一个数，使它俩的和的二分之一等于m，若存在的话，将这组数存到一数组N中，并将这组数从原2n个数组中剔除。
3、m=m+0.5；仍从第一个数开始，重复第二步（因为两个整数的和的二分之一要么是整数要么是整数点5）；
4、直到N的长度等于n时停止。

[ 本帖最后由 thuining 于 2012-7-11 10:03 编辑 ]

你没说数据范围啊，你说下n的范围以为整数的范围

int 型数据以内。。。。随便个数就可以，例如500

[ 本帖最后由 thuining 于 2012-7-11 10:21 编辑 ]

1到500，还是随便500个数

随便的500个数，但是解决这个问题，思路最好不限制在数组的数量上，因为根据需要数组长度也可能是1000。这个数组元素的数值是随意的

自己再顶上去  我想我想到办法了

我的思路是这样的:
1、对着2n个整数由小到大排列，并求平均值 aver；
2、在平均值左右一步一个的移动取数；每加入一个数计算一次已取数的平均值，若平均值大于aver左侧移动一步取数，
   小于aver在右侧移动一步取数；直到取够n个数。（若某侧数已经取全，则在另一侧取数）；
3、若平均值aver左侧数被取全；则直接输出结果；结束！
   若平均值aver右侧数被取全；
     ①求所选数的均值aver1;若aver1<aver;或者aver1=aver;直接输出结果；结束！
4、若两侧均未被取全；
    求所选数的均值aver1;若aver1>aver;计算|aver1-aver|*n；取将选取的n个数中与没选取的n个数之差ai-aj
    最接近(aver1-aver)*n；用aj替换ai计算平均值aver2；若|aver1-aver|>|aver2-aver1|，将ai利用aj替换，重复该
    步骤;否则输出结果，结束！
     

这道题有一个关键词：最接近

按以下步骤：
1.将2n个数求各，并求出这2n个数总和的二分之一（设这个值为a）;
2.将2n个数排序。如从小以大排序；
3.按从大到小依次逐个累加这2n个数（用b表示），当累加到某个数，出现b>a,则跳过这个数，继续累加下一个数，如此下循环下去，直到最后一个数。
 这样，可以得到最接近a，但比a小的数，这个数设为b。
4.按类似的办法，求出最接近a,但比a大的数，这个数为c。
5.比较b和c，看看哪个数更接近a。

先写这么多，迟些再修改！