Article From:https://www.cnblogs.com/airbluecat/p/9684759.html
```  1 package com.xxx.utils;
2
4
5 import java.util.*;
6
7 public class ArrayGroupUtils {
8
9     public static void main(String[] args) {
10 //        int[] arr = {5, 6, 4, 8, 7, 1, 2, 3};//4 5 6 7 8
11         int[] arr = {1, 2, 5, 6, 6, 9, 10, 17, 18, 2, 8, 20};
12         List<List<Integer>> lists = minGroup(arr, 30);
13         for (List<Integer> list : lists) {
14             System.out.println(list);
15         }
16     }
17
18
19     /**
20      * Minimum Grouping Method - Grouping numbers in arrays, requiring the sum of the numbers in each grouping to be less than or equal to k, and finding the minimum number of groupings, each number in the default arr is less than k 21      * <p>
22      * The first step is to sort the array into an ordered one. 23      * <p>
24      * The second step: from the first beginning of the array to calculate and exceed K, these are divided into one group. Then we start to calculate the sum of the next group, and finally to the end of the array. 25      * <p>
26      * The third step: now each group of I has a D[i] to K distance. Now remove all the D[i] of all other groups except the first group. 27      * Starting with the largest number in the first packet, place it in the other packet that holds this number and is the smallest distance from K to D [i]. This process is called division. After splitting, we need to reschedule. 28      * <p>
29      * Termination condition: if the first group is split completely, then second groups are split like this. Until a group can not be split. 30      *
31      * @param arr
32      * @param k
33      */
34     public static List<List<Integer>> minGroup(int[] arr, int k) {
35         //Get ascending list
36         List<Integer> list = Ints.asList(arr);
37         Collections.sort(list);
38
39         //Sublist
40         List<List<Integer>> subList = new ArrayList<>();//-->List<Map<Integer,List> >
42
43
44         Integer temp = 0;
45         List<Integer> tempList = new ArrayList<>();
46
47
48         for (Integer integer : list) {
49
50             if ((temp + integer) < k) {
52                 temp += integer;
53             } else if ((temp + integer) > k) {
54                 temp = integer;
56                 tempList = new ArrayList<>();
58             } else {
60                 temp = 0;
62                 tempList = new ArrayList<>();
63             }
64
65
66         }
68
69
70         for (int m = 0; m < subList.size(); m++) {
71             division(subList, resultList, k, m);
72         }
73
74         //Processing 0 elements in sublist
75         List<List<Integer>> handZeroEleList = handZeroEle(subList);
76
77         return handZeroEleList;
78
79
80     }
81
82
83     private static void division(List<List<Integer>> subList, List<List<Integer>> resultList, int k, int m) {
84
85         /*The map for generating D[i]: List is in D[i] ascending order (except for the first grouping).*/
86         List<Map<Integer, List>> mapList = getSortedList(subList, k, m);
87
88         //Traversing all elements under the first group
89         List<Integer> subList1 = subList.get(m);
90         Collections.reverse(subList1);
91
92         for (int n = 0; n < subList1.size(); n++) {
93             Integer integer = subList1.get(n);
94             for (int j = 0; j < mapList.size(); j++) {
95                 Map<Integer, List> listMap = mapList.get(j);
96                 Integer diTemp = getFirstKey(listMap);
97                 List<Integer> listTemp = getFirstValue(listMap);
98                 if (integer > diTemp) {//If you can't put in, compare the next group.
99                     continue;
100                 } else {//If you can just put it in, repeat the sorting --> continue the loop.101                     //To Riga
102                     listMap.remove(diTemp);
103                     diTemp -= integer;
105                     listMap.put(diTemp, listTemp);
106
107                     //Delete in the first group.108                     //it.remove();
109 //                    integer =  0;
110                     subList1.set(n, 0);
111
112                     sortByCustom(mapList);
113                     break;
114
115                 }
116             }
117         }
119
120     }
121
122
123     /**
124      * Get rid of the first packet and sort all other packets by D[i].125      *
126      * @param subList
127      * @param k
128      * @return
129      */
130     private static List<Map<Integer, List>> getSortedList(List<List<Integer>> subList, int k, int m) {
131         List<Map<Integer, List>> mapList = new ArrayList<>();
132         for (int i = m + 1; i < subList.size(); i++) {
133             Map<Integer, List> tempMap = new HashMap<>();
134             tempMap.put(k - listSum(subList.get(i)), subList.get(i));
136         }
137         sortByCustom(mapList);
138         return mapList;
139     }
140
141
142     /**
143      * sort144      *
145      * @param mapList
146      * @return
147      */
148     private static void sortByCustom(List<Map<Integer, List>> mapList) {
149         Collections.sort(mapList, new Comparator<Map<Integer, List>>() {
150             @Override
151             public int compare(Map<Integer, List> o1, Map<Integer, List> o2) {
152                 if (getFirstKey(o1) > getFirstKey(o2)) {
153                     return 1;
154                 }
155                 if (getFirstKey(o1) == getFirstKey(o2)) {
156                     return 0;
157                 }
158                 return -1;
159             }
160         });
161     }
162
163
164     /**
165      * Seek array and166      *
167      * @param arr
168      * @return
169      */
170     public static int arraySum(int[] arr) {
171         int sum = 0;
172         for (int i : arr) {
173             sum += i;
174         }
175         return sum;
176     }
177
178     /**
179      * Seek list< integer> sum.180      *
181      * @param list
182      * @return
183      */
184     public static Integer listSum(List<Integer> list) {
185         Integer sum = 0;
186         for (Integer integer : list) {
187             sum += integer;
188         }
189         return sum;
190     }
191
192
193     /**
194      * Get the first key value in map195      *
196      * @param map data source197      * @return
198      */
199     private static Integer getFirstKey(Map<Integer, List> map) {
200         Integer obj = null;
201         for (Map.Entry<Integer, List> entry : map.entrySet()) {
202             obj = entry.getKey();
203             if (obj != null) {
204                 break;
205             }
206         }
207         return obj;
208     }
209
210
211     /**
212      * Get the first data value in map213      *
214      * @param map data source215      * @return
216      */
217     private static List getFirstValue(Map<Integer, List> map) {
218         List obj = null;
219         for (Map.Entry<Integer, List> entry : map.entrySet()) {
220             obj = entry.getValue();
221             if (obj != null) {
222                 break;
223             }
224         }
225         return obj;
226     }
227
228
229     /**
230      * [0, 6, 6, 5, 0, 0]231      * [0, 0, 17, 10]
232      * [2, 1, 9, 18]0 of it goes away.233      *
234      * @param subList
235      */
236     private static List<List<Integer>> handZeroEle(List<List<Integer>> subList) {
237         List<List<Integer>> resultList = new ArrayList<>();
238         for (List<Integer> integers : subList) {
239             List<Integer> list = new ArrayList<>();
240             for (Integer integer : integers) {
241                 if (integer != 0) {