将M个数分为N组(M>N)，保证N组之间的数之和几乎相等

将M个数分为N组(M>N)，保证N组之间的数之和几乎相等；

花了点时间，虽然很简单的一个命题。其实最多1个小时就可写完的事，由于粗心，花了3个小时才调完。

 

package com.xiva;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

import org.junit.Test;

/**
 * @Description 假定needSortNum个数，分为groupsNum组
 * @author XGT
 *
 */
public class Subgroup {

	List<Integer> numList = new ArrayList<Integer>();
	
	List<Integer> cloneList = new ArrayList<Integer>();
	
	//平均数
	Long averageNum = 0l;
	
	//需要分组的个数
	static int needSortNum = 100000;
	
	//组数
	static int groupsNum = 213;
	
	//数据产生范围
	static int range = 10000000;
	
	//当前存储的组数
	int currGroup = 0;
	
	Map<Integer, List<Integer>> resultMap = new HashMap<Integer, List<Integer>>();
	
	
	/**
	 * 随即产生range以内的needSortNum个数字
	 */
	private void genarateNum(){
		for (int i=0; i<needSortNum; i++){
			Random ran     = new Random(System.nanoTime());
			int randNum    = ran.nextInt(range);
			Integer numObj = Integer.valueOf(randNum);
			numList.add(numObj);
		}
	}
	
	/**
	 * 进行从小到大的排序
	 */
	private void sortNum(){
		
		Object[] numArray =  numList.toArray();
		Arrays.sort(numArray);
		int length = numArray.length;
		for (int i=0; i<length; i++){
			numList.set(i, Integer.valueOf(numArray[i].toString()));
		}
		System.out.println("最大值："+numList.get(numList.size()-1)+"最小值："+numList.get(0));
	}
	
	/**
	 * 计算平均值
	 */
	private void setAverageNum(){
		long totalNum = 0l;
		int size = numList.size();
		for (int i=0; i<size; i++){
			totalNum = totalNum + numList.get(i);
		}
		averageNum = totalNum/groupsNum;
	}
	
	
	/**
	 * 开始分组
	 */
	private void start2Divide(){
		
		cloneList.addAll(numList);
		
		int size = numList.size();
		long groupTempNum = 0l;
		
		int currIndex = size-1;
		
		List<Integer> tempList = new ArrayList<Integer>();
		while(cloneList.size() > 0){
			groupTempNum = groupTempNum + cloneList.get(currIndex);
			if(groupTempNum < averageNum){
				tempList.add(cloneList.get(currIndex));
				cloneList.remove(currIndex);
				currIndex = currIndex -1;
			}else{
				long groupNum = groupTempNum - cloneList.get(currIndex);
				
				while(groupNum < averageNum){
					long difference2 = averageNum -  groupNum;
					int index2 = getSuitedIndex(difference2, cloneList);
					if (index2 == 0)
						break;
					Integer suitedObj2 = cloneList.get(index2);
					
					tempList.add(cloneList.get(index2));
					cloneList.remove(index2);
					currIndex = currIndex -1;
					
					groupNum = groupNum + suitedObj2;
				}
				
				storeList2Map(tempList);
				groupTempNum = 0;
			}
			
			if(currGroup == groupsNum-1){
				doTheRestNum();
				break;
			}
		}
	}
	
	
	/**
	 * @Description 返回与差值比较小的index
	 * @param difference
	 * @param cloneList
	 * @return
	 */
	private int getSuitedIndex(long difference, List<Integer> cloneList){
		int size = cloneList.size();
		int reIndex = 0;
		
		for (int i=0; i<size; i++){
			long currAbs = difference - cloneList.get(i);
			if ( currAbs > 0){
				continue;
			}else{
				reIndex = i;
				break;
			}
		}
		if (reIndex==0){
			System.out.println("这样就最小了~");
			reIndex = 0;
		}
		else{
			if (Math.abs(difference - cloneList.get(reIndex-1)) < Math.abs(difference - cloneList.get(reIndex)) )
			{
				reIndex = reIndex -1;
			}
		}
		return reIndex;
	}
	
	/**
	 * @Description 将分组的数据保存到Map
	 * @param tempList
	 */
	private void storeList2Map(List<Integer> tempList){
		List<Integer> gourpList = new ArrayList<Integer>();
		gourpList.addAll(tempList);
		currGroup = currGroup + 1;
		resultMap.put(Integer.valueOf(currGroup), gourpList);
		tempList.clear();
	}
	
    /**
     * 处理余下来的数据
     */
	private void doTheRestNum(){
		int size = cloneList.size();
		if ( size > 0){
			List<Integer> tempList = new ArrayList<Integer>();
			for (int i=0; i<size; i++){
				tempList.add(cloneList.get(i));
			}
			resultMap.put(Integer.valueOf(currGroup+1), tempList);
		}
	}
	
	private void printAllResult(){
		Set<Map.Entry<Integer, List<Integer>>> entrySet = resultMap.entrySet();
        Iterator<Map.Entry<Integer, List<Integer>>> iterator = entrySet.iterator();
        int total = 0;
        System.out.println("平均数：" + averageNum);
        while  (iterator.hasNext()) {  
            Map.Entry<Integer, List<Integer>> map = iterator.next();
            List<Integer> list = map.getValue();
            long totalNum = 0l;
            for(Integer obj:list){
            	totalNum = totalNum + obj;
//            	System.out.print(obj+";");
            }
            System.out.println();
            System.out.println("第"+map.getKey()+"组，"+"个数为：" + list.size()+"，总值为："+totalNum+"差值为："+(totalNum-averageNum));
            total = total + list.size();
        }  
        System.out.println(total);
	}
	
	@Test public void testSorted(){
		
		genarateNum();
		sortNum();
		setAverageNum();
		start2Divide();
		printAllResult();
	}

}

 主要核心方法在于排序，取值的方法以及getSuitedIndex()这个方法。

这个是一个基本的解决方法，也可以基于这个程序之上，再写一个调优算法，保证最终结果正在趋于理想。

 

调优算法的思想是根据本组与平均值的差值去找其他组的元素相交换。