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