m个数分为n组，使每组的和近似相等（C++版本）

话不多说，直接上代码，其中有个排序，可调用，也可不调用，调用了排序后，分组时小数容易扎堆分到一组，不排序相对于排序的分组效果更均匀。

// testvs2.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <unordered_map>
#include <vector>
#include <iostream>
#include <math.h>
#include<stdio.h>
#include<stdlib.h>
#define random(x) (rand()%x)
using namespace std;


/// 随即产生range以内的needSortNum个数字
void genarateNum(int needSortNum,vector<double> &numList)
{
    for (int i = 0; i < needSortNum; i++)
    {
        int numObj = random(10);
        numList.push_back(numObj);
    }
}

/// 进行从小到大的排序
void sortNum(vector<double> &numList)
{
    for(int i = 1;i < numList.size();++i)
    {
        for(int j = i;j > 0;--j)
        {
            if(numList[j] < numList[j - 1])
            {
                double temp = numList[j];
                numList[j] = numList[j-1];
                numList[j-1] = temp;
            }
        }
    }
    std::wcout << L"最大值：" << numList[numList.size() - 1] << L"最小值：" << numList[0] << std::endl;
}


/// 计算平均值
double setAverageNum(vector<double> &numList,int groupsNum)
{
    double totalNum = 0;
    int size = numList.size();
    for (int i = 0; i < size; i++)
    {
        totalNum = totalNum + numList[i];
    }
    double averageNuma = totalNum / groupsNum;
    return averageNuma;
}

/// 返回与差值比较小的index 
int getSuitedIndex(double difference, std::vector<double> &cloneList)
{
    int size = cloneList.size();
    int reIndex = 0;

    for (int i = 0; i < size; i++)
    {
        double currAbs = difference - cloneList[i];
        if (currAbs > 0)
        {
            continue;
        }
        else
        {
            reIndex = i;
            break;
        }
    }
    if (reIndex == 0)
    {
        std::wcout << L"这样就最小了~" << std::endl;
        reIndex = 0;
    }
    else
    {
        if (std::abs(difference - cloneList[reIndex - 1]) < std::abs(difference - cloneList[reIndex]))
        {
            reIndex = reIndex - 1;
        }
    }
    return reIndex;
}

///将分组的数据保存到Map
void storeList2Map(std::vector<double> &tempList,int &currGroup,std::unordered_map<int, std::vector<double>> &resultMap)
{
    std::vector<double> gourpList;
    gourpList.insert(gourpList.end(), tempList.begin(), tempList.end());
    currGroup = currGroup + 1;
    resultMap.emplace(std::make_pair(currGroup, gourpList));
    tempList.clear();
}

/// 处理余下来的数据
void doTheRestNum(vector<double> cloneList,int &currGroup,std::unordered_map<int, std::vector<double>> &resultMap)
{
    int size = cloneList.size();
    if (size > 0)
    {
        std::vector<double> tempList;
        for (int i = 0; i < size; i++)
        {
            tempList.push_back(cloneList[i]);
        }
        resultMap.emplace(std::make_pair((currGroup + 1), tempList));
    }
}

/// 开始分组
void start2Divide(vector<double> numList,double averageNum,int groupsNum,std::unordered_map<int, std::vector<double>> &resultMap)
{
    int currGroup=0;
    vector<double> cloneList;
    cloneList.insert(cloneList.end(), numList.begin(), numList.end());

    int size = numList.size();
    double groupTempNum = 0;

    int currIndex = size-1;

    std::vector<double> tempList;
    while (cloneList.size() > 0)
    {
        groupTempNum = groupTempNum + cloneList[currIndex];
        if (groupTempNum < averageNum)
        {
            tempList.push_back(cloneList[currIndex]);
            cloneList.erase(cloneList.begin() + currIndex);
            currIndex = currIndex - 1;
        }
        else
        {
            double groupNum = groupTempNum - cloneList[currIndex];

            while (groupNum < averageNum)
            {
                double difference2 = averageNum - groupNum;
                int index2 = getSuitedIndex(difference2, cloneList);
                if (index2 == 0)
                {
                    break;
                }
                double suitedObj2 = cloneList[index2];

                tempList.push_back(cloneList[index2]);
                cloneList.erase(cloneList.begin() + index2);
                currIndex = currIndex - 1;

                groupNum = groupNum + suitedObj2;
            }

            storeList2Map(tempList,currGroup,resultMap);
            groupTempNum = 0;
        }

        if (currGroup == groupsNum - 1)
        {
            doTheRestNum(cloneList,currGroup,resultMap);
            break;
        }
    }
}

//输出分组情况
void printAllResult(vector<double> numList,std::unordered_map<int, std::vector<double>> resultMap)
{
    //输出随机产生的数
    for(int i=0;i<numList.size();i++)
    {
        cout<<numList[i]<<" ";
    }
    cout<<endl<<endl;

    //输出每组的分组情况及其和
    auto iter = resultMap.begin();//auto自动识别为迭代器类型unordered_map<int,string>::iterator
    while (iter!= resultMap.end())
    {  
        double sum=0;
        for(int i=0;i<iter->second.size();i++)
        {
            cout << iter->second[i] << " ";  
            sum+=iter->second[i];
        }
                
        cout<<"        其总和为： "<<sum<<endl;
        ++iter;  
    }  
}


/// <summary>
/// @Description 假定needSortNum个数，分为groupsNum组
/// </summary>
void testSorted(int needSortNum,int groupsNum)
{
    vector<double> numList;//原始数据
    std::unordered_map<int, std::vector<double>> resultMap;//分组结果
    genarateNum(needSortNum,numList);
    //sortNum();//不排序，分的个数比较均匀，否则小的数容易分到一组里
    double averageNum=setAverageNum(numList,groupsNum);
    start2Divide(numList,averageNum,groupsNum,resultMap);
    printAllResult(numList,resultMap);
}


int _tmain(int argc, _TCHAR* argv[])
{
    testSorted(96,5);
    return 0;

}