作者：胡满超 来源：C++博客 酷勤网收集 2008-04-18
摘要
把一堆数平均分成N份，保证每一份的和接近于所有数之和除以N，不要求平分以后的每份数据个数相等。这是有现实的程序设计需求的，当时是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];
}
}
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的测试工程，有兴趣的朋友点此下载。
理论的依据不仅指导了实践的选择，同时给选择以有力的支撑。
来自：http://www.cppblog.com/humanchao/archive/2007/12/29/39934.html