一年半之前，我遇到一個問題：把一堆數平均分成N份，保證每一份的和接近于所有數之和除以N，不要求平分以后的每份數據個數相等。這是有現實的程序設計需求的，當時是3份。首先想到要先進行排序，再依次從已排序的數列中抽取，如何進行抽取方法有很多，我大概想了3種左右，感覺要拿一些數據去測試一下這幾種方法哪一種可以逼近最優解。
當時經理要求算法一定能夠得出最優解，但測試多組數據，沒有發現哪一種實現能得到最優解。后來翻了一下
《數據結構、算法與應用--C++語言描述》，忽然想到，原來這個是一個典型貪婪算法問題，這個問題沒有最優解，用貪婪算法來解決這個問題可以讓每一次結果逼近最優。實現如下(注：代碼是我今天寫的)：
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的測試工程，有興趣的朋友
點此下載。
理論的依據不僅指導了實踐的選擇，同時給選擇以有力的支撐。
2007年就要結束了，在此預祝大家在新的一年里：身體健康，平安如意！
posted on 2007-12-29 15:52
胡滿超 閱讀(4155)
評論(12) 編輯 收藏 引用