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