一年半之前，我遇到一個問題：把一堆數(shù)平均分成N份，保證每一份的和接近于所有數(shù)之和除以N，不要求平分以后的每份數(shù)據(jù)個數(shù)相等。這是有現(xiàn)實的程序設(shè)計需求的，當(dāng)時是3份。首先想到要先進(jìn)行排序，再依次從已排序的數(shù)列中抽取，如何進(jìn)行抽取方法有很多，我大概想了3種左右，感覺要拿一些數(shù)據(jù)去測試一下這幾種方法哪一種可以逼近最優(yōu)解。
當(dāng)時經(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)如下(注：代碼是我今天寫的)：
typedef vector<int> IntVector;
typedef vector<IntVector> IntMat;
void DeuceNumber(const IntVector &SourceVecNum,
const int nShare,
IntMat &OutVecVecNum)
{
IntVector copySourceNum = SourceVecNum;
sort(copySourceNum.begin(), copySourceNum.end(), greater<int>());
IntVector sum(nShare);
OutVecVecNum.resize(nShare);
for (int i = 0; i < copySourceNum.size(); i++)
{
const int nMinSumPos = min_element(sum.begin(), sum.end()) - sum.begin();
OutVecVecNum[nMinSumPos].push_back(copySourceNum[i]);
sum [nMinSumPos] += copySourceNum[i];
}
}
我上傳了一個VC的測試工程，有興趣的朋友
點此下載。
理論的依據(jù)不僅指導(dǎo)了實踐的選擇，同時給選擇以有力的支撐。
2007年就要結(jié)束了，在此預(yù)祝大家在新的一年里：身體健康，平安如意！
posted on 2007-12-29 15:52
胡滿超 閱讀(4167)
評論(12) 編輯 收藏 引用