任意数分三组,使得每组的和尽量相等

题目：任意数分三组,使得每组的和尽量相等
思路：第一次遇到这个题目的时候，那叫一个难字，对于算法题，算法本身可能并没有什么，但是如何获得求解算法的思路是一个关键。对于本题，我们可以采用归纳总结的方法。比如，任意数组分成一组，使得每组的和尽量相等。任意的数组分成两组，使得每组的和尽量相等。从这两个基本的问题，我们容易知道，如果数组总和整除分组数的商就是分组后的和（如果可以实现的话，多数情况是接近），当然还有一个极端的情况，比如数组中的最大值，大于这个商，这时候，我们可以使用降纬的方法，把其中一个分组的值设置成这个最大值，对于剩下的值采用同样的思路。（这个使用反证法很容易证明的）

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<int> vec_int;
typedef vector<vector<int> > vec_vec_int;

void Output(int nNum)
{
    cout << nNum  << " ";
}

void Output2(const vec_int & vecNum)
{
    for_each(vecNum.begin(), vecNum.end(), Output);
    cout << endl;
}

void CalZu(vec_vec_int & vecZu, int nZu, const vec_int & vecNum, int nBegin)
{
    if (vecNum.size() <= nBegin) return;

    int nSum = 0;
    int nAvg = 0;
    for (int i=nBegin; i<vecNum.size(); ++i) 
        nSum += vecNum[i];

    nAvg = nSum / nZu;
    if (nSum % nZu != 0)
        nAvg += 1;

    if (nAvg < vecNum[nBegin]) {
        vecZu[nZu-1].push_back(vecNum[nBegin]);
        CalZu(vecZu, nZu-1, vecNum, nBegin+1);
    } else {
        vec_int vecSum(nZu, nAvg);
        for (int i=nBegin; i<vecNum.size(); ++i) {
            int k = 0;
            int nTmpMin = vecSum[k] - vecNum[i];
            for (int j=1; j<vecSum.size(); ++j) {
                int nTmp = vecSum[j] - vecNum[i];
                if ((nTmpMin < 0 && nTmp >=  0)
                    || (nTmpMin < 0 && nTmpMin < nTmp)
                    || (nTmp > 0 && nTmpMin > nTmp) ) {
                    nTmpMin = nTmp;
                    k = j;
                }
            }
            vecZu[k].push_back(vecNum[i]);
            vecSum[k] -= vecNum[i];
        }
    }
}

int main(int argc, char ** argv)
{
    int a[] = {9, 8, 6, 6, 6, 5, 6, 5};
    // int a[] = {1003, 1002, 103, 102, 101, 3, 2, 1};
    int aLen = sizeof(a) / sizeof(int);

    vec_int vecNum(a, a+aLen);

    sort(vecNum.begin(), vecNum.end(), greater<int>());

    cout << "Input:" << endl;
    for_each(vecNum.begin(), vecNum.end(), Output); 
    cout << endl;

    const int nZu = 3;

    vec_vec_int vecZu(nZu);

    CalZu(vecZu, nZu, vecNum, 0);

    cout << "Output:" << endl;
    for_each(vecZu.begin(), vecZu.end(), Output2);
}