一年半之前，我遇到一个问题：把一堆数平均分成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
胡满超 阅读(4113)
评论(12) 编辑 收藏 引用