🎯目的：
1）了解回溯算法思想；
2）掌握回溯法的算法框架；
3）能够针对实际问题，按照回溯法算法框架，分析问题的解空间、解空间的组织结构、搜索的约束条件、限界条件；
4）能够正确的编码；
5）能够正确分析算法的时间复杂度和空间复杂度。
🎯内容概括：
- 使用回溯法解决n皇后问题：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
- 0-1背包问题的回溯算法与分支限界算法的实现：给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为W。一个物品要么全部装入背包，要么全部不装入背包，不允许部分装入。装入背包的物品的总重量不超过背包的容量。问应如何选择装入背包的物品，使得装入背包中的物品总价值最大？
例如：物品数目n=4，限重W=7，物品重量分别为w=(3,5,2,1)，价值为v=(9,10,7,4)，最优解为：（1，0，1，1）。
🎯基本步骤：
1）明确题目的已知条件和求解的目标；
2）问题建模；
3）算法设计；
4）编码实现；
5）测试数据；
6）程序运行结果；
7）分析实验结果是否符合预期，如果不符合，分析可能的原因；
8）算法分析。
🎯内容：
🐟one：
🎐问题：
使用回溯法解决n皇后问题：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
🎐解题思路：
- 创建一个大小为n×n的棋盘。
- 从第一行开始，在每一行选择一个位置放置皇后，保证不受攻击。
- 在放置皇后的过程中，需要检查当前位置是否满足放置条件，即不与之前放置的皇后冲突。
- 如果找到一个满足条件的位置，继续递归地在下一行放置皇后。
- 如果在某一行无法找到合适的位置，回溯到上一行，尝试放置皇后的其他位置。
- 当所有行都放置了皇后，得到一个解。
- 继续回溯，寻找其他解。
🎐代码分析：
package test20210110; public class Test01 { public static void main(String[] args) { NQueens nQueens = new NQueens(); nQueens.solveNQueens(4); } }
这段代码定义了一个Test01类，包含了程序入口main方法。在main方法中创建了一个NQueens的实例，并调用solveNQueens方法，传入参数4，表示要解决4皇后问题。
class NQueens { private int[] queens; // 皇后在每一行的列索引 private int n; // 棋盘大小 public void solveNQueens(int n) { this.n = n; queens = new int[n]; backtrack(0); } private void backtrack(int row) { if (row == n) { // 打印解决方案 printQueens(); return; } for (int col = 0; col < n; col++) { if (isValid(row, col)) { queens[row] = col; backtrack(row + 1); } } } private boolean isValid(int row, int col) { for (int i = 0; i < row; i++) { if (queens[i] == col || queens[i] - col == i - row || queens[i] - col == row - i) { return false; } } return true; } private void printQueens() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (queens[i] == j) { System.out.print("Q "); } else { System.out.print(". "); } } System.out.println(); } System.out.println(); } }
这段代码定义了一个NQueens类，用于解决N皇后问题。类中包含了solveNQueens方法、backtrack方法、isValid方法和printQueens方法。
solveNQueens方法用于解决N皇后问题，接受一个整数参数n，表示要解决的棋盘大小。在方法中，首先初始化queens数组和n变量，然后调用backtrack方法，传入参数0，表示从第0行开始搜索。
backtrack方法用于使用回溯算法来解决N皇后问题。接受一个整数参数row，表示当前处理的行数。
如果row等于n，即已经处理完所有行，就打印出解决方案，即调用printQueens方法，并返回。
否则，对于当前行的每一列，判断是否能够放置皇后，即调用isValid方法。
如果可以放置皇后，就将列索引记录在queens数组中，并递归调用backtrack方法处理下一行。
isValid方法用于判断当前位置是否可以放置皇后。遍历之前的行，检查是否与之前的皇后冲突。如果与之前的皇后冲突，返回false；否则，返回true。
printQueens方法用于打印解决方案。遍历每一行和每一列，根据queens数组中的列索引来输出相应的字符（"Q"代表皇后，"."代表空格）。每打印完一行，就换行，并在最后打印一个空行。
🎐总代码：
package test20210110; public class Test01 { public static void main(String[] args) { NQueens nQueens = new NQueens(); nQueens.solveNQueens(4); } } class NQueens { private int[] queens; // 皇后在每一行的列索引 private int n; // 棋盘大小 public void solveNQueens(int n) { this.n = n; queens = new int[n]; backtrack(0); } private void backtrack(int row) { if (row == n) { // 打印解决方案 printQueens(); return; } for (int col = 0; col < n; col++) { if (isValid(row, col)) { queens[row] = col; backtrack(row + 1); } } } private boolean isValid(int row, int col) { for (int i = 0; i < row; i++) { if (queens[i] == col || queens[i] - col == i - row || queens[i] - col == row - i) { return false; } } return true; } private void printQueens() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (queens[i] == j) { System.out.print("Q "); } else { System.out.print(". "); } } System.out.println(); } System.out.println(); } }
🐟two：
🎐 问题：
0-1背包问题的回溯算法与分支限界算法的实现：给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为W。一个物品要么全部装入背包，要么全部不装入背包，不允许部分装入。装入背包的物品的总重量不超过背包的容量。问应如何选择装入背包的物品，使得装入背包中的物品总价值最大？
例如：物品数目n=4，限重W=7，物品重量分别为w=(3,5,2,1)，价值为v=(9,10,7,4)，最优解为：（1，0，1，1）。
🎐解题思路：
回溯算法：
- 使用回溯算法可以尝试所有可能的解决方案，找到总价值最大的解。
- 从第一个物品开始，逐个考虑将其放入背包或不放入背包的情况。
- 对于每个物品，如果放入背包不超重，则递归地考虑下一个物品，并更新当前总价值。
- 当考虑完所有物品或背包已满时，比较当前总价值与历史最大总价值，更新最大总价值和最优解。
- 通过递归回溯，可以尝试所有可能的组合，最终找到最优解。
分支限界算法：
- 使用分支限界算法可以更高效地找到最优解。
- 使用优先队列来维护待扩展的节点，节点的优先级根据上界来确定，上界越大表示该节点可能包含更优解。
- 从根节点开始，依次扩展节点，生成子节点。
- 对于每个子节点，计算其上界，如果上界大于当前的最优解，将子节点加入优先队列。
- 通过不断扩展和剪枝，优先队列中的节点会按照优先级被处理，直到队列为空或无法生成更优的节点。
- 当队列为空时，得到的最优解即为问题的解。
🎐代码分析：
第一部分：导入相关包
package one; import java.util.*;
这部分代码用于导入所需的包，包括java.util包，以便使用ArrayList、LinkedList和Collections等类。
第二部分：定义物品类
Item和节点类Node
private static class Item implements Comparable<Item> { int weight; int value; double density; public Item(int weight, int value) { this.weight = weight; this.value = value; this.density = (double) value / weight; } @Override public int compareTo(Item other) { return Double.compare(other.density, this.density); } } private static class Node { int level; int weight; int value; double bound; public Node(int level, int weight, int value, double bound) { this.level = level; this.weight = weight; this.value = value; this.bound = bound; } }
这部分代码定义了两个内部类 Item 和 Node。 Item 类表示背包中的物品，有重量(weight)、价值(value)和价值密度(density)属性。 Node 类表示搜索树上的节点，具有层级(level)、总重量(weight)、总价值(value)和价值上界(bound)属性。
第三部分：解决背包问题的方法 solveKnapsack
public static int solveKnapsack(int maxWeight, int[] weights, int[] values) { // ... 省略部分代码 ... }
这部分代码定义了一个静态方法 solveKnapsack，用于解决背包问题。它接受最大承重(maxWeight)、物品重量数组(weights)和物品价值数组(values)作为输入参数，并返回最优解的最大价值。
第四部分：计算价值上界的方法
bound
private static double bound(int level, int weight, int value, List<Item> items, int maxWeight) { // ... 省略部分代码 ... }
这部分代码定义了一个私有静态方法 bound，用于计算给定节点的价值上界。它接受层级(level)、当前总重量(weight)、当前总价值(value)、物品列表(items)和最大承重(maxWeight)作为输入参数，并返回价值上界。
第五部分：主函数 main
public static void main(String[] args) { // ... 省略部分代码 ... }
这部分代码定义了主函数 main，在其中创建了一个具体的背包问题实例，调用 solveKnapsack 方法求解最大价值，并输出结果。
🎐总代码：
package one; import java.util.*; public class Knapsack { private static class Item implements Comparable<Item> { int weight; int value; double density; public Item(int weight, int value) { this.weight = weight; this.value = value; this.density = (double) value / weight; } @Override public int compareTo(Item other) { return Double.compare(other.density, this.density); } } private static class Node { int level; int weight; int value; double bound; public Node(int level, int weight, int value, double bound) { this.level = level; this.weight = weight; this.value = value; this.bound = bound; } } public static int solveKnapsack(int maxWeight, int[] weights, int[] values) { int n = weights.length; List<Item> items = new ArrayList<>(); for (int i = 0; i < n; i++) { items.add(new Item(weights[i], values[i])); } Collections.sort(items); Queue<Node> queue = new LinkedList<>(); Node root = new Node(-1, 0, 0, 0); queue.offer(root); int maxValue = 0; while (!queue.isEmpty()) { Node node = queue.poll(); int level = node.level + 1; int weight = node.weight; int value = node.value; if (level == n) { if (value > maxValue) { maxValue = value; } continue; } if (weight + items.get(level).weight <= maxWeight) { int newValue = value + items.get(level).value; if (newValue > maxValue) { maxValue = newValue; } queue.offer(new Node(level, weight + items.get(level).weight, newValue, node.bound)); } if (bound(level + 1, weight, value, items, maxWeight) > maxValue) { queue.offer(new Node(level, weight, value, bound(level + 1, weight, value, items, maxWeight))); } } return maxValue; } private static double bound(int level, int weight, int value, List<Item> items, int maxWeight) { double bound = value; int n = items.size(); int totalWeight = weight; while (level < n && totalWeight + items.get(level).weight <= maxWeight) { bound += items.get(level).value; totalWeight += items.get(level).weight; level++; } if (level < n) { bound += (maxWeight - totalWeight) * items.get(level).density; } return bound; } public static void main(String[] args) { int[] weights = {3, 5, 2, 1}; int[] values = {9, 10, 7, 4}; int maxWeight = 7; int maxValue = solveKnapsack(maxWeight, weights, values); System.out.println("The maximum value that can be obtained: " + maxValue); } }
