|
|
输入箱子体积：[3233, 6549, 7402, 8436] 大于【19421】的最小子集和为:[6549, 3233, 3233, 3233, 3233]
[code]package com.dam.combinationProblem.question4;
import java.util.Arrays;
import java.util.LinkedList;
public class MySolution {
private int minValue = Integer.MAX_VALUE;
private LinkedList<Integer> bestPath = new LinkedList<>();
public static void main(String[] args) {
long start = System.currentTimeMillis();
int[] smallLengthArr = new int[]{3233, 6549, 7402, 8436};
int max = 500000;
MySolution solution = new MySolution();
solution.combinationSum(smallLengthArr, max, solution);
System.out.println("最优方案:" + solution.bestPath.toString());
System.out.println("最小值:" + solution.minValue);
long end = System.currentTimeMillis();
System.out.println("计算时间:" + (end - start) + "ms");
}
public void combinationSum(int[] smallLengthArr, int max, MySolution solution) {
int length = smallLengthArr.length;
//初始化needNum
int[] needNum = new int[length];
for (int i = 0; i < needNum.length; i++) {
needNum[i] = max / smallLengthArr[i] + 1;
}
System.out.println("如果只使用一种箱子，需要的数量" + Arrays.toString(needNum));
//拓展数组
int arrLen = 0;
for (int i = 0; i < needNum.length; i++) {
arrLen += needNum[i];
}
int len = smallLengthArr.length;
if (len == 0 || arrLen == 0) {
System.out.println("输出数据有问题");
}
//降序排序，后面剪枝更多
shellSort(smallLengthArr);
// Arrays.sort(smallLengthArr);
//最终数组
int[] lastSmallLengthArr = new int[arrLen];
int count = 0;
for (int i = 0; i < smallLengthArr.length; i++) {
for (int j = 0; j < needNum[i]; j++) {
lastSmallLengthArr[count++] = smallLengthArr[i];
}
}
// System.out.println("最终数组:" + Arrays.toString(lastSmallLengthArr));
LinkedList<Integer> path = new LinkedList<>();
dfs(lastSmallLengthArr, 0, max, solution, 0, arrLen, path);
}
private void dfs(int[] lastSmallLengthArr, int value, int max, MySolution solution, int begin, int length, LinkedList<Integer> path) {
//当数组遍历完成，说明该节点已经拓展完成
if (begin == length) {
return;
}
//从begin开始，相当于前面的元素已经使用
for (int i = begin; i < length; i++) {
// 大剪枝：所使用的箱子组合的体积已经大于最优体积，直接break即可
if (value + lastSmallLengthArr[i] > solution.minValue) {
break;
}
// 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
if (i > begin && lastSmallLengthArr[i] == lastSmallLengthArr[i - 1]) {
continue;
}
path.addLast(lastSmallLengthArr[i]);
//说明找到了解，且解更优，则更新最优解
if (value + lastSmallLengthArr[i] >= max && value + lastSmallLengthArr[i] < solution.minValue) {
solution.bestPath = (LinkedList<Integer>) path.clone();
solution.minValue = value + lastSmallLengthArr[i];
}
dfs(lastSmallLengthArr, value + lastSmallLengthArr[i], max, solution, i + 1, length, path);
path.removeLast();
}
}
//希尔排序--降序排序
private static void shellSort(int[] arr) {
for (int step = arr.length / 2; step > 0; step /= 2) {
for (int i = step; i < arr.length; i++) {
int value = arr[i];
int j;
for (j = i - step; j >= 0 && arr[j] < value; j -= step) {
arr[j + step] = arr[j];
}
arr[j + step] = value;
}
}
}
}
[/code] |
|
发表于 2024-6-22 09:46:18
发表于 2024-8-6 10:42:43
