回溯算法第一篇（子集树问题【三种思路】、0-1背包问题、最小重量机器设计问题）

目录1. 子集树问题解法一解法二解法三2. 0-1背包问题使用子集树解决3. 最小重量机器设计问题1. 子集树问题子集力扣链接题目描述给你一个整数数组nums数组中的元素互不相同。返回该数组所有可能的子集幂集。解集不能包含重复的子集。你可以按任意顺序返回解集。示例 1输入nums [1,2,3]输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2输入nums [0]输出[[],[0]]提示1 nums.length 10-10 nums[i] 10nums中的所有元素互不相同注子集是不能重复的例如{1,2,3}和{3,2,1}是一个子集。解决方案如下解法一算法策略为判断当前位置选还是不选则决策树的形状是二叉树决策树如下注以下代码不是力扣那道题的正确代码需要自行修改一些方法名解法二的代码就可以在力扣运行且通过所有测试import java.util.ArrayList; import java.util.List; //子集的第一种结果叶子结点收集 public class SubsetTest { //设计全局变量 static ListInteger path;//用来临时接受一次自己的情况 static ListListInteger ret;//用来接收全部子集情况 //nums表示需要计算子集的数组 //deep表示第几层也是表示nums数组的第几个元素有两种选择选还是不选 public static void permute(int[] nums, int deep) { //1.初始化 path new ArrayList(); ret new ArrayList(); //2.开始进行回溯算法 dfs(nums, deep); } public static void output() { ret.add(new ArrayList(path)); } public static void dfs(int[] nums, int deep) { //递归出口 if (deep nums.length) { output(); return; } else {//这回溯的核心写成决策树是一颗二叉树因为有两种选择 //1选 path.add(nums[deep]); //进入下一层 dfs(nums, deep 1); //恢复现场移除最后一个元素 path.remove(path.size() - 1); //2不选因为不选没有改变path集合所以不需要恢复现场 dfs(nums, deep 1); } } public static void main(String[] args) { int[] nums {1, 2, 3}; permute(nums, 0); for (int i 0; i ret.size(); i) { System.out.println(ret.get(i)); } } }解法二算法的策略相交于第一种解法有所不同第一种解法是判断当前位置选不选的情况所以决策树的叶子结点才是子集。第二种解法是一棵多叉的决策树是从一个子集的容量问题上来分情况例如子集里面的元素可以是0个、1个、2个也可以是3个。具体如下所示class Solution { ListInteger path;//用来记录一次的子集 ListListInteger ret;//用来记录总的子集情况 public ListListInteger subsets(int[] nums) { //1.初始化 path new ArrayList(); ret new ArrayList(); //2.回溯的核心 dfs(nums, 0); return ret; } //nums需要计算子集的数组 //deep表示当前来到树的第几层 public void dfs(int nums[], int deep) { //因为每一个结点都是我需要的结果所以每一个结点都要收集 ret.add(new ArrayList(path)); //回溯开始 //这里必须从deep开始表示在nums数组中的第几位开始 //只有这样才不会导致重复选取 for (int i deep; i nums.length; i) { path.add(nums[i]); dfs(nums, i 1); //恢复现场 path.remove(path.size() - 1); } } }解法三解法三是在解法一的思路上加上一个boolean数组来判断当前位置选没选决策树如下public class Test10 { static int N 3; static char[] a {a, b, c}; static boolean[] x {false, false, false}; public static void main(String[] args) { backTrack(0); } //回溯的核心 public static void backTrack(int level) { if (level N) { output(); } else { x[level] false;//不选 backTrack(level 1); x[level] true; backTrack(level 1); } } //打印数据 public static void output() { System.out.print({); for (int i 0; i x.length; i) { //如果这个位置是选的话也就是x[i] true就选a[i] if (x[i]) { System.out.print(a[i] ); } } System.out.print(}); System.out.println(); } }2. 0-1背包问题使用子集树解决题目描述你有⼀个背包最多能容纳的体积是V。现在有 n 个物品第 i 个物品的体积为vi价值为wi。1求这个背包⾄多能装多⼤价值的物品2若背包恰好装满求⾄多能装多⼤价值的物品true表示选这物品false表示不选这物品public class Test11 { static int C 30;//背包容量 static int N 3;//三个物品 static int weights[] {16, 15, 15};//重量 static int values[] {45, 25, 25};//价值 static boolean[] x {false, false, false};//作为判断选不选的问题 //保存最大价值 static int maxValuse 0; //回溯核心 //w当前背包所放物品重量和 //v当前背包所放物品价值和 public static void backtrack(int level, int w, int v) { if (level N) { output(v); } else { x[level] false;//不选 backtrack(level 1, w, v); x[level] true;//选 if (legal(w weights[level])) backtrack(level 1, w weights[level], v values[level]); } } //判断当前背包重量是不是合法 public static boolean legal(int w) { return w C; } //v当前的价值 public static void output(int v) { maxValuse Math.max(v, maxValuse); } public static void main(String[] args) { backtrack(0, 0, 0); System.out.println(maxValuse); } }3. 最小重量机器设计问题题目描述设某一机器由 N 个部件组成每一种部件都可以从 M 个不同的供应商处购得。设 W 是从供应商j处购得的部件i的重量, C 是相应的价格。 试设计一个算法给出总价格不超过 D 的最小重量机器设计。解决方案如下public class Test12 { static int N 3;//部件数 static int Suppliers 3;//供应商数 static int D 4;//总价格限制 static int minWeight Integer.MAX_VALUE;//这个变量用来保存最小重量 static int[][] weight {{1, 2, 3}, {3, 2, 1}, {2, 1, 2}};//重量数组 static int[][] value {{1, 2, 3}, {3, 2, 1}, {2, 2, 2}};//价格数组 static int[] str new int[3]; /* false表示选true表示不选 */ //默认值是false //为什么是二维数组呢因为要与w和v二维数组对应 static boolean[][] flag new boolean[3][3]; //打印每个零件的供应商 public static void output() { for (int i 0; i N; i) { for (int j 0; j Suppliers; j) { if (flag[i][j]) str[i] j 1; } } } /* w表示当前的重量 v表示当前的价值 level表示层数0表示选第一个零件、1表示选第二个零件、2表示选第三个零件 */ public static void backtrack(int level, int w, int v) { //能走到这个if肯定是没超过限制重量D if (level N) { int tmp minWeight; minWeight Math.min(minWeight, w); if (tmp ! minWeight) { output(); } } else { //表示从第一个供应商开始选择 for (int i 0; i Suppliers; i) { flag[level][i] true; if (D v value[level][i]) { backtrack(level 1, w weight[level][i], v value[level][i]); } //这个为什么要改为false呢 //方便output方法的实现找到每个零件的供应商 flag[level][i] false; } } } public static void main(String[] args) { backtrack(0, 0, 0); System.out.println(最小重量 minWeight); System.out.print(供应商顺序); for (int i 0; i str.length; i) { System.out.print(str[i] ); } } }