怎么樣把一堆數平均分成N份
摘要: 一年半之前，我遇到一個問題：把一堆數平均分成N份，保證每一份的和接近于所有數之和除以N，不要求平分以后的每份數據個數相等。這是有現實的程序設計需求的，當時是3份。首先想到要先進行排序，再依次從已排序的數列中抽取，如何進行抽取方法有很多，我大概想了3種左右，感覺要拿一些數據去測試一下這幾種方法哪一種可以逼近最優解。
當時經理要求算法一定能夠得出最優解，但測試多組數據，沒有發現哪一種實現能得到最優解。后來翻了一下《數據結構、算法與應用--C++語言描述》，忽然想到，原來這個是一個典型貪婪算法問題，這個問題沒有最優解，用貪婪算法來解決這個問題可以讓每一次結果逼近最優。實現如下(注：代碼是我今天寫的)：
閱讀全文
posted @
2007-12-29 15:52 胡滿超 閱讀(4180) |
評論 (12) 編輯