问题一：给定一特定长度的原材料，和客户的需求，如何获取可行的原材料方案？
问题描述
如原材料长度为8，需要切割出长度为4，3，1的片段各4根（需求数量），请问有多少种切割方案？如方案有：[4,4],[4,3,1],[4,1,1,1,1]……
注意：切割方案中的子料数量不能大于需求数量，且所有子料的长度累计要小于等于原料长度，如需要切割出长度为4，3，1的片段各1根，则方案[4,1,1,1,1]被抛弃，因为其中长度为1的子料数量是4，已经超出需求数量1。
回溯法求解
package com.dam.combinationProblem.question3;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class MySolution {
public static void main(String[] args) {
long start = System.currentTimeMillis();
int[] smallLengthArr = new int[]{1380, 1520, 1560, 1710, 1820, 1880, 1930, 2000, 2050, 2100, 2140, 2150, 2200};
int[] needNum = new int[]{22, 25, 12, 14, 18, 18, 20, 10, 12, 14, 16, 18, 20};
int max = 5600;
MySolution solution = new MySolution();
List<LinkedList<Integer>> res = solution.combinationSum(smallLengthArr, needNum, max);
// System.out.println("输出 => " + res);
System.out.println("方案数量:" + res.size());
long end = System.currentTimeMillis();
System.out.println("计算时间:" + (end - start) + "ms");
}
public List<LinkedList<Integer>> combinationSum(int[] smallLengthArr, int[] needNum, int max) {
//拓展数组
int arrLen = 0;
for (int i = 0; i < needNum.length; i++) {
arrLen += needNum[i];
}
//无须切割
int len = smallLengthArr.length;
List<LinkedList<Integer>> result = new ArrayList<>();
if (len == 0 || arrLen == 0) {
System.out.println("输出数据有问题");
return result;
}
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, 0, arrLen, path, result);
return result;
}
private void dfs(int[] lastSmallLengthArr, int value, int max, int begin, int length, LinkedList<Integer> path, List<LinkedList<Integer>> result) {
//当数组遍历完成，说明该节点已经拓展完成
if (begin == length) {
return;
}
//从begin开始，相当于前面的元素已经使用
for (int i = begin; i < length; i++) {
// 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
if (value + lastSmallLengthArr[i] > max) {
break;
}
// 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
if (i > begin && lastSmallLengthArr[i] == lastSmallLengthArr[i - 1]) {
continue;
}
path.addLast(lastSmallLengthArr[i]);
//说明找到了解
if (value + lastSmallLengthArr[i] <= max) {
//保存解
result.add((LinkedList<Integer>) path.clone());
}
dfs(lastSmallLengthArr, value + lastSmallLengthArr[i], max, i + 1, length, path, result);
path.removeLast();
}
}
}
数据1
原材料长度为8，需要切割出长度为4，3，1的片段各10根
输出结果：
方案数量:20
[1]
[1, 1]
[1, 1, 1]
[1, 1, 1, 1]
[1, 1, 1, 1, 3]
[1, 1, 1, 1, 4]
[1, 1, 1, 3]
[1, 1, 1, 4]
[1, 1, 3]
[1, 1, 3, 3]
[1, 1, 4]
[1, 3]
[1, 3, 3]
[1, 3, 4]
[1, 4]
[3]
[3, 3]
[3, 4]
[4]
[4, 4]
计算时间:1ms数据2
原材料长度为5600，需要子料长度为{1380,1520,1560,1710}，其对应的数量分别为{5,4,2,2}
输出结果：
方案数量:33
[1380]
[1380, 1380]
[1380, 1380, 1380]
[1380, 1380, 1380, 1380]
[1380, 1380, 1520]
[1380, 1380, 1560]
[1380, 1380, 1710]
[1380, 1520]
[1380, 1520, 1520]
[1380, 1520, 1560]
[1380, 1520, 1710]
[1380, 1560]
[1380, 1560, 1560]
[1380, 1560, 1710]
[1380, 1710]
[1380, 1710, 1710]
[1520]
[1520, 1520]
[1520, 1520, 1520]
[1520, 1520, 1560]
[1520, 1520, 1710]
[1520, 1560]
[1520, 1560, 1560]
[1520, 1560, 1710]
[1520, 1710]
[1520, 1710, 1710]
[1560]
[1560, 1560]
[1560, 1560, 1710]
[1560, 1710]
[1560, 1710, 1710]
[1710]
[1710, 1710]
计算时间:1ms问题二：求解出和处于上下限之间的所有组合
回溯法
package com.dam.combinationProblem.question2;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class MySolution {
public static void main(String[] args) {
int[] smallLengthArr = new int[]{3, 5, 1};
int[] needNum = new int[]{2, 2, 2};
int min = 4;
int max = 6;
MySolution solution = new MySolution();
List<LinkedList<Integer>> res = solution.combinationSum(smallLengthArr, needNum, min, max);
System.out.println("输出 => " + res);
}
public List<LinkedList<Integer>> combinationSum(int[] smallLengthArr, int[] needNum, int min, int max) {
//拓展数组
int arrLen = 0;
for (int i = 0; i < needNum.length; i++) {
arrLen += needNum[i];
}
//无须切割
int len = smallLengthArr.length;
List<LinkedList<Integer>> result = new ArrayList<>();
if (len == 0 || arrLen == 0) {
System.out.println("输出数据有问题");
return result;
}
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, min, max, 0, arrLen, path, result);
return result;
}
private void dfs(int[] lastSmallLengthArr, int value, int min, int max, int begin, int length, LinkedList<Integer> path, List<LinkedList<Integer>> result) {
//当数组遍历完成，说明该节点已经拓展完成
if (begin == length) {
return;
}
//从begin开始，相当于前面的元素已经使用
for (int i = begin; i < length; i++) {
if (value + lastSmallLengthArr[i] > max) {
break;
}
if (i > begin && lastSmallLengthArr[i] == lastSmallLengthArr[i - 1]) {
continue;
}
path.addLast(lastSmallLengthArr[i]);
//说明找到了解
if (value + lastSmallLengthArr[i] >= min && value + lastSmallLengthArr[i] <= max) {
//保存解
result.add((LinkedList<Integer>) path.clone());
}
dfs(lastSmallLengthArr, value + lastSmallLengthArr[i], min, max, i + 1, length, path, result);
path.removeLast();
}
}
}
结果：
处理之后的数组：[1, 1, 3, 3, 5, 5]
输出 => [[1, 1, 3], [1, 3], [1, 5], [3, 3], [5]]问题三：获取所有和为目标数的组合
问题描述
给定一个数字集合，需要从数字集合中挑选出部分数字形成子集，子集的和等于目标数。问：如何找出符合要求的所有子集？
如数字集合为[1,1,1,2]，目标数是3，则子集有[1,1,1]、[1,2]。
回溯法
package com.dam.combinationProblem.question1;
import java.util.*;
public class MySolution {
public static void main(String[] args) {
// int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
int[] candidates = new int[]{10, -1, 2, -7, 6, 1, -5};
int target = 8;
/*int[] candidates = new int[]{2, 5, 2, 1, 0};
int target = 5;*/
MySolution solution = new MySolution();
List<LinkedList<Integer>> res = solution.combinationSum(candidates, target);
System.out.println("输出 => " + res);
}
public List<LinkedList<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
List<LinkedList<Integer>> result = new ArrayList<>();
if (len == 0) {
return result;
}
Arrays.sort(candidates);
System.out.println(Arrays.toString(candidates));
LinkedList<Integer> path = new LinkedList<>();
dfs(candidates, target, candidates.length, 0, path, result);
return result;
}
private void dfs(int[] candidates, int target, int length, int begin, LinkedList<Integer> path, List<LinkedList<Integer>> result) {
//当数组遍历完成，说明该节点已经拓展完成
if (begin == length) {
return;
}
//从begin开始，相当于前面的元素已经使用
for (int i = begin; i < length; i++) {
if (target - candidates[i] < 0) {
break;
}
if (i > begin && candidates[i] == candidates[i - 1]) {
continue;
}
path.addLast(candidates[i]);
//说明找到了解，无需往下拓展
if (target - candidates[i] == 0) {
//保存解
result.add((LinkedList<Integer>) path.clone());
path.removeLast();
return;
}
dfs(candidates, target - candidates[i], length, i + 1, path, result);
path.removeLast();
}
}
}
结果：
[-7, -5, -1, 1, 2, 6, 10]
输出 => [[-7, -1, 6, 10], [-5, 1, 2, 10], [-1, 1, 2, 6], [2, 6]]问题四：搜索大于 19421的最小组合：19481
输入箱子体积：[3233, 6549, 7402, 8436] 大于【19421】的最小子集和为:[6549, 3233, 3233, 3233, 3233]
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;
}
}
}
}
