四：回溯法-皇后问题
4.1 概念
- 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
- n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
4.2 画图表示
可行解示例：
过程构造示例：
4.3 代码实现
4.3.1 实现思路
宏观：
使用深度搜索的方法，按照先行后列的顺序，查看每一个位置是否满足条件。
微观：
定义二维数组表示棋盘，定义一个变量n表示几个皇后
定义一个方法用来判断当前摆放的皇后是否与之前的皇后冲突（同列、左上方，右上方)，冲突返回0；否则，返回1，表示此位置可以放置皇后。
定义一个递归函数，尝试在当前行放置皇后。
4.3.2 具体代码
package com.lsn.NQueen; public class NQueens { // 定义一个二维数组表示棋盘 int[][] board; // 定义一个变量表示几个皇后 int n; // 构造函数，初始化棋盘和n public NQueens(int n) { board = new int[n][n]; this.n = n; } // 判断当前摆放的皇后是否与之前的皇后冲突 public boolean isSafe(int row, int col) { int i, j; // 检查当前列是否有皇后 for (i = 0; i < row; i++) { if (board[i][col] == 1) { return false; } } // 检查左上方是否有皇后 for (i = row, j = col; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 1) { return false; } } // 检查右上方是否有皇后 for (i = row, j = col; i >= 0 && j < n; i--, j++) { if (board[i][j] == 1) { return false; } } // 如果都没有冲突，则返回true return true; } // 递归函数，尝试在当前行放置皇后 public boolean solve(int row) { // 如果所有行都已经摆放完毕，则返回true（终止条件，收集结果） if (row == n) { return true; } // 尝试在当前行的每一列放置皇后（单层逻辑，处理节点） for (int col = 0; col < n; col++) { // 判断当前位置是否安全 if (isSafe(row, col)) { // 如果安全，则将皇后放置在当前位置 board[row][col] = 1; // 递归调用solve函数，尝试在下一行放置皇后 if (solve(row + 1)) { return true; } // 如果下一行无法放置皇后，则回溯到当前行，重新尝试放置皇后（撤销处理节点的情况） board[row][col] = 0; } } // 如果当前行的每一列都无法放置皇后，则返回false return false; } // 打印棋盘 public void printBoard() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.print(board[i][j] + " "); } System.out.println(); } } public static void main(String[] args) { // 创建一个NQueens对象，并初始化规模为8 NQueens nQueens = new NQueens(3); // 调用solve函数，尝试解决N皇后问题 if (nQueens.solve(0)) { // 如果找到了解，则打印棋盘 nQueens.printBoard(); } else { // 如果没有找到解，则打印无解 System.out.println("无解."); } } }
通过上述代码，我们可以搜索到皇后的一个可行解。
4.4 总结提升
皇后问题也是回溯法的一种体现。它使用了回溯法提高效率的减枝策略，不符合条件的就不必向下进行递归，大大的提高了算法的效率。相较于上文给出二叉树回溯法的例子，它更加的复杂，体现的是一个二维的搜索，但是其核心思想都是回溯。
五：贪心法
5.1 概念
总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。
贪心法体现：Djikstra（迪杰斯特拉）算法，构造最小生成树的Prim（普里姆）算法和Kruskal（克鲁斯卡尔）算法
算法目的 将一个大的任务拆分成若干个小的任务逐个解决来完成拆分之前总任务的效果。
算法过程
把求解的问题分成若干个子问题
对每个子问题求解，得到子问题的局部最优解
把子问题的解局部最优解合成原来问题的一个解
该算法存在的问题
1.不能保证求得的最后解是最佳的
2.只能求满足某些约束条件的可行解的范围
5.2 画图表示
5.3 代码实现
5.3.1 题目描述
给你一个整数数组 ，请你找出一个具有的连续子数组最大和（子数组最少包含一个元素），返回其最大和。
注意：子数组是数组中的一个连续部分。
5.3.2 java代码
public class MaximumSubarray { public int maxSubArray(int[] nums) { int currentSum = 0; // 当前子数组的和 int maxSum = Integer.MIN_VALUE; // 最大子数组的和 // 遍历数组中的每个元素 for (int num : nums) { // 如果当前子数组的和加上当前元素小于当前元素本身，那么当前子数组的和不再对后续子数组产生正向影响，重新开始一个新的子数组 currentSum = Math.max(num, currentSum + num); // 更新最大子数组的和 maxSum = Math.max(maxSum, currentSum); } return maxSum; } public static void main(String[] args) { int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 }; MaximumSubarray solution = new MaximumSubarray(); int maxSum = solution.maxSubArray(nums); System.out.println("最大和为：" + maxSum); } }
在以上代码中，我们使用贪心法的思想，从数组的第一个元素开始遍历，计算当前子数组的和 currentSum 和最大子数组的和 maxSum。在每次遍历过程中，我们用 Math.max(num, currentSum + num) 更新 currentSum 的值，这样可以保证 currentSum 始终是以当前元素结尾的最大子数组的和。同时，我们用 Math.max(maxSum, currentSum) 更新 maxSum 的值，以保证最终得到的 maxSum 是整个数组中的最大子数组和。
5.4 总结提升
贪心法是一种求解问题的策略，其核心思想是在每一步选择中都采取当前状态下最优的选择，从而希望最终达到全局最优解。贪心法通常适用于满足「最优子结构」和「贪心选择性质」的问题。
总结贪心法的思想可以归纳为以下几点：
最优子结构（Optimal Substructure）：问题的最优解包含了子问题的最优解。这意味着通过选择当前最优的解，可以将原问题拆分为更小的子问题，并且每个子问题的最优解可以组合成原问题的最优解。
贪心选择性质（Greedy Choice Property）：在每一步选择中，采取当前最优的选择，即局部最优解，希望通过局部最优解达到全局最优解。这意味着贪心法不会回退或撤销之前的选择，而是根据当前情况做出决策。
不可回退（不考虑后效性）：贪心法做出的选择一旦确定就不可更改，不会对之前的选择进行修改。它只关注当前状态下的最优选择，并相信通过每一步的最优选择能够达到整体最优。
需要注意的是，贪心法并不适用于所有问题，因为某些问题无法通过贪心的方式获得最优解。在使用贪心法时，需要经过严格的推导和证明，以确保其正确性。
贪心法的优点是简单、高效，并且通常可以在较短的时间内得到一个近似最优解。然而，其缺点是不能保证一定能够得到全局最优解，因此在某些情况下可能得到次优解或错误的结果。
总而言之，贪心法通过选择当前最优解来逐步构建问题的解决方案，希望通过局部最优解达到全局最优解。它是一种简单而高效的求解问题的策略，但需要仔细分析问题的性质和特点，以确定贪心选择和最优子结构的存在性。
六：动态规划
6.1 概念
将待求问题划分为若干个子问题，按划分的顺序求解子阶段问题，前一个子问题的解，为后一个子问题的求解提供了有用的信息（最优子结构）。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其它局部解。依次解决各个子问题，最后求出原问题的最优解
6.2 画图表示
这里以一个斐波那契数列举例
6.3 代码实现
6.3.1 实现思路
1.定义一个要求的斐波那契数
2.判断求的斐波那契数是否小于等于1，是的话直接返回求的斐波那契数，否的话，则创建一个数组，用来记录子问题的解
3.初始化第一个斐波那契数值，和第二个斐波那契数值。求第三个斐波那契数值的时候，把前两个下标的值进行相加，得出第三个斐波那契的数值。依次按照这种方式，最终得出需要求的斐波那契数值
6.3.2 具体代码
public class Fibonacci { public static void main(String[] args) { int numberArr = 10; // 求第10个斐波那契数 int result = fibonacci(numberArr); // 第10个斐波那契数的值 System.out.println("第10个斐波那契数值为："+ result); // 输出第10个斐波那契数的值 } /** * 斐波那契数列的动态规划算法 * @paramn 第numberArr个斐波那契数，dp为数据处理后的值 * @return 第numberArr个斐波那契数的值 */ public static int fibonacci(int numberArr) { if (numberArr <= 1) { // 当numberArr小于等于1时，直接返回numberArr return numberArr; } //创建数组，用于记录子问题的解 //dp为数据处理后的值 int[] dp = new int[numberArr + 1]; dp[0] = 0; // 初始化第一个数 dp[1] = 1; // 初始化第二个数 // 递推求解子问题 for (int i = 2; i <= numberArr; i++) { //dp[i]:i为该求下标 //dp[i-1]:i为该求下标-1的下标的值 //dp{[i-2]:i为该求下标-2的下标的值 //算出两个下标的值后进行相加，最后得出该求下标的值 dp[i] = dp[i - 1] + dp[i - 2]; System.out.println("第"+i+"轮numberArr的值为"+ dp[i]); } // 返回第numberArr个斐波那契数的值 return dp[numberArr]; } }
6.4 总结提升
动态规划（Dynamic Programming）是一种将复杂问题分解为更小子问题并以递推的方式求解的方法。它通常适用于具有「最优子结构」和「重叠子问题」性质的问题。
简单总结动态规划法的思想可以归纳为以下几点：
最优子结构（Optimal Substructure）：问题的最优解可以通过子问题的最优解来构建。这意味着原问题的解可以由相关子问题的解组合而成。
重叠子问题（Overlapping Subproblems）：在递归求解过程中，许多子问题会被重复计算多次。动态规划利用记忆化或者自底向上的方法，将子问题的解存储起来以避免重复计算，提高效率。
状态转移方程（State Transition Equation）：动态规划通过定义状态和状态之间的转移方程来描述问题的求解过程。状态转移方程表示问题的当前状态与前一状态之间的关系，通过状态转移方程来推导出最优解。
自底向上的计算顺序：动态规划通常使用自底向上的计算顺序，从最小规模的子问题开始逐步求解，直到推导出原问题的解。这样可以保证所有的子问题在求解时都已经得到解决。
动态规划的优点是能够求解复杂问题并得到最优解，避免了重复计算，提高了计算效率。然而，动态规划的缺点是需要较大的空间来存储中间结果，有时会牺牲一定的空间复杂性来换取时间上的优化。
总而言之，动态规划通过将复杂问题分解为更小的子问题并以递推的方式求解，利用最优子结构和重叠子问题的性质，通过状态转移方程来推导最优解。它是一种常用的求解优化问题的方法，能够高效地求解多种问题。
七：动态规划-0/1背包问题
7.1 概念
7.1.1 例子
用一个例子来说明0/1背包问题：
现有四个物品，小偷背包总容量为8，怎么样可以偷走价值最多的物品
物品编号：1 2 3 4
物品重量：2 3 4 5
物品价值：3 4 5 8
7.1.2 限定
各种限定条件解决问题：
部分背包问题：所有物品是可再分的，即允许将某件物品的一部分（例如 1/3）放入背包；
0-1 背包问题：所有物品不可再分，要么整个装入背包，要么放弃，不允许出现“仅选择物品的 1/3 装入背包”的情况；
完全背包问题：不对每一件物品的数量做限制，同一件物品可以选择多个装入背包；
7.2 画图表示
7.3 代码实现
public static void main(String[] args) { String[] nameArr = {"鞋子", "音响", "电脑"}; // 商品重量数组 int[] weightArr = {1/*鞋子*/, 4/*音响*/, 3/*电脑*/}; // 商品价格数组 int[] priceArr = {1500/*鞋子*/, 3000/*音响*/, 2000/*电脑*/}; // 背包容量 int packageCapacity = 4; backpackWithoutRepeat(nameArr, weightArr, priceArr, packageCapacity); } private static void backpackWithoutRepeat(String[] nameArr, int[] weightArr, int[] priceArr, int packageCapacity) { /** * 声明一个能装入 0、1、2、3磅......的背包的二维价格表；举例：就好比 v数组是表2的数据 */ int[][] nameBackpack = new int[nameArr.length + 1][packageCapacity + 1]; // 构建可能装入背包的二维数组 // 值为0时说明不会装进背包, 值为1说明可能装入背包 int[][] contentArr = new int[nameArr.length + 1][packageCapacity + 1]; /** * 为什么i一开始是1不是0？看表2的数据，是不是第一行全是0啊 */ for (int i = 1; i < nameBackpack.length; i++) { /** * 为什么j一开始是1不是0？看表2的数据，是不是第一列全是0啊 */ System.out.println(nameBackpack[i]); for (int j = 1; j < nameBackpack[i].length; j++) { /** * 文章中当 w[i] > j 时，就有 nameBackpack[i][j] = nameBackpack[i-1][j]； * 因为我们程序i是从1开始的，因此原来公式中的w[i]修改成w[i-1]； * 当前商品 > 背包容量, 取同列上一行数据 */ if (weightArr[i - 1] > j) { nameBackpack[i][j] = nameBackpack[i - 1][j]; } else { /** * 当前商品 <= 背包容量, 对两部分内容进行比较; * 第一部分, 该列上一行数据 */ int onePart = nameBackpack[i - 1][j]; /** * 还记得文章中写的 当j >= w[i] 时，有 nameBackpack[i][j]=max{nameBackpack[i-1][j],nameBackpack[i-1][j-w[i]]+nameBackpack[i]} 这个公式成立吗？ * priceArr[i - 1]: 当前商品价格; * w[i - 1]: 当前商品重量; * j - w[i - 1]: 去掉当前商品, 背包剩余容量; * 不可重复: nameBackpack[i - 1][j - w[i - 1]]: 在上一行, 取剩余重量下的价格最优解; */ int otherPart = priceArr[i - 1] + nameBackpack[i - 1][j - weightArr[i - 1]]; /** * 取最大值为当前位置的最优解 */ nameBackpack[i][j] = Math.max(onePart, otherPart); /** * 如果最优解包含当前商品, 则表示当前商品已经被使用, 进行记录 */ if (otherPart == nameBackpack[i][j]) { contentArr[i][j] = 1; } } } } // 不能重复的场景中 // 如果该位置的标志位为1, 说明该商品参与了最终的背包添加 // 如果该位置的标志位为0, 即使该位置的价格为最大价格, 也是从其他位置引用的价格 // 因为不能重复, 所以每行只取一个数据参与最终计算, 并只判断在最大位置该商品是否参与 // 该最大位置会随着已经遍历出其他元素而对应不断减小, 直到为0 // 二维数组最后一个元素必然是最大值, 但是需要知道该最大值是自身计算的 还是比较后引用其他的 int totalPrice = 0; // 最大行下标数, 即商品数 int maxLine = contentArr.length - 1; // 最大列下标数, 即重量 int maxColumn = contentArr[0].length - 1; for (;maxLine > 0 && maxColumn > 0;) { // 等于1表示在该位置该商品参与了计算 if (contentArr[maxLine][maxColumn] == 1) { // 遍历后, 对重量减少, 下一次从剩余重量中取参与商品 maxColumn -= weightArr[maxLine - 1]; totalPrice += priceArr[maxLine - 1]; System.out.println(nameArr[maxLine - 1] + "加入了背包"); } // 因为不能重复 // 所以如果该商品参与了背包容量, 则肯定剩余的最大位置处参与, // 否则跟该数据无关, 直接跳过 maxLine--; } System.out.println("背包可容纳的最大价值: " + totalPrice); }
7.4 总结提升
动态规划的思想可以用以下步骤来解决01背包问题：
定义状态：设dp[i][j]表示在前i个物品中，背包容量为j时的最大总价值。
初始化：将dp数组初始化为0，即dp[i][j]=0，其中0≤i≤N，0≤j≤W。
状态转移方程：对于第i个物品，有两种选择：放入背包或不放入背包。
如果wi > j，即当前物品的重量大于背包容量，无法放入背包，则dp[i][j] = dp[i-1][j]，即不放入该物品时的最大价值与前i-1个物品相同。
如果wi ≤ j，即当前物品的重量小于等于背包容量，可以选择放入或不放入背包。比较两种情况下的最大价值，取较大值：
放入背包：dp[i][j] = dp[i-1][j-wi] + vi，即放入当前物品的价值加上前i-1个物品中容量为j-wi时的最大价值。
不放入背包：dp[i][j] = dp[i-1][j]，即不放入当前物品时的最大价值。
遍历计算：使用双重循环遍历物品和背包容量，根据状态转移方程更新dp数组的值。
结果输出：最终的最大总价值为dp[N][W]，其中N为物品的个数，W为背包的容量。
总结&提升
通过对算法的学习，利于锻炼我们的逻辑思维，并且指导开发，希望此篇博客可以让大家学会这几种经典的算法，领略其中的思想，应用到实践中。
