算法最少分组法-将数组arr中的数字分组，要求各个分组中数字之和小于等于k，求最小分组数的情况，默认arr中每个数均小于k...-程序员宅基地

package com.xxx.utils;

import com.google.common.primitives.Ints;

import java.util.*;

public class ArrayGroupUtils {

    public static void main(String[] args) {
//        int[] arr = {5, 6, 4, 8, 7, 1, 2, 3};//4 5 6 7 8
        int[] arr = {1, 2, 5, 6, 6, 9, 10, 17, 18, 2, 8, 20};
        List<List<Integer>> lists = minGroup(arr, 30);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }


    /**
     * 最少分组法-将数组arr中的数字分组，要求各个分组中数字之和小于等于k，求最小分组数的情况，默认arr中每个数均小于k
     * <p>
     * 第一步：排序，将数组先折腾成有序的（升序）。
     * <p>
     * 第二步：从数组第一个开始计算和，超过K了，这些就分一组。然后开始计算下一组的和，最后直到数组的末尾。
     * <p>
     * 第三步：现在每一组i都有一个到K距离的D[i]。现在除去第一个分组外将所有其它分组的D[i]进行排序。
     * 从第一个分组中最大的数开始扫描，将它放置到能够容纳这个数的，距离K的D[i]最小的其它分组中。这个过程我称为分裂。分裂完成后要重新排序。
     * <p>
     * 终止条件：如果第一个分组全部分裂完成了，则再这样分裂第二个分组。直到某个分组不能分裂为止。
     *
     * @param arr
     * @param k
     */
    public static List<List<Integer>> minGroup(int[] arr, int k) {
        //获取升序的list
        List<Integer> list = Ints.asList(arr);
        Collections.sort(list);

        //子list
        List<List<Integer>> subList = new ArrayList<>();//-->List<Map<Integer,List> >
        List<List<Integer>> resultList = new ArrayList<>();//返回结果


        Integer temp = 0;
        List<Integer> tempList = new ArrayList<>();


        for (Integer integer : list) {

            if ((temp + integer) < k) {
                tempList.add(integer);
                temp += integer;
            } else if ((temp + integer) > k) {
                temp = integer;
                subList.add(tempList);
                tempList = new ArrayList<>();
                tempList.add(integer);
            } else {
                tempList.add(integer);
                temp = 0;
                subList.add(tempList);
                tempList = new ArrayList<>();
            }


        }
        subList.add(tempList);//加上最后一个数


        for (int m = 0; m < subList.size(); m++) {
            division(subList, resultList, k, m);
        }

        //处理sublist中为0的元素
        List<List<Integer>> handZeroEleList = handZeroEle(subList);

        return handZeroEleList;


    }


    private static void division(List<List<Integer>> subList, List<List<Integer>> resultList, int k, int m) {

        /*生成D[i]:List的map按D[i]升序(除了第一个分组)*/
        List<Map<Integer, List>> mapList = getSortedList(subList, k, m);

        //遍历第一个分组下的所有元素
        List<Integer> subList1 = subList.get(m);
        Collections.reverse(subList1);

        for (int n = 0; n < subList1.size(); n++) {
            Integer integer = subList1.get(n);
            for (int j = 0; j < mapList.size(); j++) {
                Map<Integer, List> listMap = mapList.get(j);
                Integer diTemp = getFirstKey(listMap);
                List<Integer> listTemp = getFirstValue(listMap);
                if (integer > diTemp) {
    //不能放进去，则比较下一个分组
                    continue;
                } else {
    //正好能放进去,则重新进行排序-->继续循环
                    //往里加
                    listMap.remove(diTemp);
                    diTemp -= integer;
                    listTemp.add(integer);
                    listMap.put(diTemp, listTemp);

                    //往第一个分组里删除
                    //it.remove();
//                    integer =  0;
                    subList1.set(n, 0);

                    sortByCustom(mapList);
                    break;

                }
            }
        }
        resultList.add(subList1);

    }


    /**
     * 获取除去第一个分组外将所有其它分组按D[i]进行排序
     *
     * @param subList
     * @param k
     * @return
     */
    private static List<Map<Integer, List>> getSortedList(List<List<Integer>> subList, int k, int m) {
        List<Map<Integer, List>> mapList = new ArrayList<>();
        for (int i = m + 1; i < subList.size(); i++) {
            Map<Integer, List> tempMap = new HashMap<>();
            tempMap.put(k - listSum(subList.get(i)), subList.get(i));
            mapList.add(tempMap);
        }
        sortByCustom(mapList);
        return mapList;
    }


    /**
     * 排序
     *
     * @param mapList
     * @return
     */
    private static void sortByCustom(List<Map<Integer, List>> mapList) {
        Collections.sort(mapList, new Comparator<Map<Integer, List>>() {
            @Override
            public int compare(Map<Integer, List> o1, Map<Integer, List> o2) {
                if (getFirstKey(o1) > getFirstKey(o2)) {
                    return 1;
                }
                if (getFirstKey(o1) == getFirstKey(o2)) {
                    return 0;
                }
                return -1;
            }
        });
    }


    /**
     * 求数组和
     *
     * @param arr
     * @return
     */
    public static int arraySum(int[] arr) {
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        return sum;
    }

    /**
     * 求list<integer>和
     *
     * @param list
     * @return
     */
    public static Integer listSum(List<Integer> list) {
        Integer sum = 0;
        for (Integer integer : list) {
            sum += integer;
        }
        return sum;
    }


    /**
     * 获取map中第一个key值
     *
     * @param map 数据源
     * @return
     */
    private static Integer getFirstKey(Map<Integer, List> map) {
        Integer obj = null;
        for (Map.Entry<Integer, List> entry : map.entrySet()) {
            obj = entry.getKey();
            if (obj != null) {
                break;
            }
        }
        return obj;
    }


    /**
     * 获取map中第一个数据值
     *
     * @param map 数据源
     * @return
     */
    private static List getFirstValue(Map<Integer, List> map) {
        List obj = null;
        for (Map.Entry<Integer, List> entry : map.entrySet()) {
            obj = entry.getValue();
            if (obj != null) {
                break;
            }
        }
        return obj;
    }


    /**
     * 将[0, 6, 6, 5, 0, 0]
     * [0, 0, 17, 10]
     * [2, 1, 9, 18]中的0去除掉
     *
     * @param subList
     */
    private static List<List<Integer>> handZeroEle(List<List<Integer>> subList) {
        List<List<Integer>> resultList = new ArrayList<>();
        for (List<Integer> integers : subList) {
            List<Integer> list = new ArrayList<>();
            for (Integer integer : integers) {
                if (integer != 0) {
                    list.add(integer);
                }
            }
            if (list.size() > 0) {
                resultList.add(list);
            }

        }
        return resultList;
    }

}