问一道算法题：求绝对值最小的数

anselcat

求集合中和的绝对值最小的三个数：
一个集合，例如{1，0，2，-66，-89}
那么输出应该是：{1,0,2}，因为在这个集合中，这三个数的和的绝对值最小。

scutan

http://zhidao.baidu.com/question/25273262.html
不过如何让算法更优, 就需要动点脑筋了

tyc611

用DP吧，应该跟这个问题属于同一类问题
http://blog.chinaunix.net/u/18517/showart_587783.html

freearth

这个算法稍微有些问题，应该修改成：
将原数组按符号分为两组：X中存所有的正数，Y中存所有的负数。
计算从X中取三个数的和的绝对值最小值；
计算从Y中取三个数的最小值；
计算从X中取两个数，Y中取一个数的最小值；
计算从X中取一个数，Y中取两个数的最小值；
上面所有情况中的最小值就是目标。
但是，按照这样做的话，量级是O(n*n)的。

原帖由 scutan 于 2008-9-16 21:10 发表
http://zhidao.baidu.com/question/25273262.html
不过如何让算法更优, 就需要动点脑筋了

cugb_cat

原帖由 tyc611 于 2008-9-16 21:20 发表
用DP吧，应该跟这个问题属于同一类问题
http://blog.chinaunix.net/u/18517/showart_587783.html

那最优子结构是什么呢？

hejiangx

还不如先遍历一遍，把负的变正的，然后用N个数中最大K个数的经典方法来求

cugb_cat

原帖由 hejiangx 于 2008-9-16 23:12 发表
还不如先遍历一遍，把负的变正的，然后用N个数中最大K个数的经典方法来求

这样不能保证最小啊。。

wilbur512

绝对值后排序？

wilbur512

啊 看错题了

[ 本帖最后由 wilbur512 于 2008-9-17 00:22 编辑 ]

wilbur512

啊 看错题了

[ 本帖最后由 wilbur512 于 2008-9-17 00:22 编辑 ]