随笔 - 88  文章 - 118  trackbacks - 0
<2007年12月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

留言簿(15)

随笔分类(54)

随笔档案(88)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

12 2007 档案
怎么样把一堆数平均分成N份      摘要: 一年半之前,我遇到一个问题:把一堆数平均分成N份,保证每一份的和接近于所有数之和除以N,不要求平分以后的每份数据个数相等。这是有现实的程序设计需求的,当时是3份。首先想到要先进行排序,再依次从已排序的数列中抽取,如何进行抽取方法有很多,我大概想了3种左右,感觉要拿一些数据去测试一下这几种方法哪一种可以逼近最优解。

当时经理要求算法一定能够得出最优解,但测试多组数据,没有发现哪一种实现能得到最优解。后来翻了一下《数据结构、算法与应用--C++语言描述》,忽然想到,原来这个是一个典型贪婪算法问题,这个问题没有最优解,用贪婪算法来解决这个问题可以让每一次结果逼近最优。实现如下(注:代码是我今天写的):  阅读全文
posted @ 2007-12-29 15:52 胡满超 阅读(2399) | 评论 (12)  编辑