最优组合算法

本是古典何须时尚 2022-11-22 12:51 145阅读 0赞

### 最优组合算法 ###

*   *  算法实现
     *  输出结果

> 学习Java的同学注意了！！！  
> 学习过程中遇到什么问题或者想获取学习资源的话，欢迎加入Java学习交流群，群号码：543120397 我们一起学Java！

> 需求：  
> 1.目标数组 \{10,6,5,3,10,2,1,1,6,1,1\}  
> 2.要求组合之和不能大于10，且组合最小

## 算法实现 ##

/** * @Description: 最优组合算法 * @Author zengwei * @Date 2020-11-03-18:32 **/
    public class TheBestCombineAlgorithm { 
        public static void main(String[] args){ 
            int[] arr = { 10,6,5,3,10,2,1,1,6,1,1};
            int max = 10;
    
            int[][] end = getArray(arr,max);
            for (int[] ints : end) { 
                if (ints != null) { 
                    System.out.println(Arrays.toString(ints));
                }
            }
        }
    
        private static int[][] getArray(int[] arr, int max) { 
            List<Integer> recordIndex = new ArrayList<>();//记录使用过的元素的索引位置
            int[][] finalArray = new int[arr.length][];
            //1.从左到右遍历所有元素
            int arrIndex = 0;//记录二维数组的位置
            for (int i=0;i<arr.length;i++){ //每循环一次,位置往后移动一次
                int currentElement = arr[i];
                if(recordIndex.contains(i)){ 
                    continue;//如果当前位置被使用了,跳过本次循环,进入下次循环
                }
                //判断当前元素是否已经大于后者等于10
                if(currentElement >= max){ 
                    finalArray[arrIndex] = new int[]{ currentElement};
                    //同时将当前索引位置存入到list中
                    recordIndex.add(i);
                }else{ 
                    List<Integer> element = new ArrayList<>();
                    element.add(currentElement);
                    while(currentElement <max){ 
                        //2.除了当前元素外,查找最小元素
                        int searchMinIndex = bubble(i,arr,recordIndex);
                        if(searchMinIndex == -1){ 
                            break;
                        }
                        currentElement += arr[searchMinIndex];
                        if(currentElement > max){ 
                            break;//因为如果相加大于10,说明不需要这个值了
                        }
                        //3.拼接到新的int数组中
                        element.add(arr[searchMinIndex]);
                        //4.将当前索引位置存入recordIndex中
                        recordIndex.add(searchMinIndex);
                    }
                    //JDK1.8特性 将List对象转为int[]数组
                    finalArray[arrIndex] = element.stream().mapToInt(j -> j).toArray();
                }
                arrIndex ++;
            }
            //4.存入到新的二维数组中
            return finalArray;
        }
    
        /** * 冒泡比较,查找最小元素位置 * @param i 查找开始位置 * @param arr 目标数组 * @param recordIndex 存储已经被使用的元素 * @return 返回最小元素索引位置 */
        private static int bubble(int i, int[] arr, List<Integer> recordIndex) { 
            int min = arr[i];//记录最小元素的值
            int index = -1;//记录最小元素位置
            for (;i<arr.length;i++){ 
                if(recordIndex.contains(i)){ 
                    continue;
                }
                if(min > arr[i]){ //每次都和最小值比较
                    min = arr[i];
                    index = i;
                }
            }
            return index;
        }
    }

## 输出结果 ##

> “C:\\Program Files\\Java\\jdk1.8.0\_101\\bin\\java.exe”  
> \[10\]  
> \[6, 1, 1, 1, 1\]  
> \[5, 2, 3\]  
> \[10\]  
> \[6\]  
> Process finished with exit code 0