随笔 - 89  文章 - 118  trackbacks - 0
<2017年5月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

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

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