总纲
插入排序算法
内容：
|
将数组待排序的元素依次插入到已排序部分，使已排序部分保持升序的性质。 |
伪代码：
复杂度分析：
|
时间复杂度为O(n^2)，空间复杂度为O(1)。在数据量较小的情况下，插入排序的效率不输给其他更复杂的排序算法，并且其实现简单，易于理解和编写，并且不需要额外的存储空间。 |
运行结果：
源代码：
|
import java.util.Arrays; public class InsertionSort { public static void insertionSort(int[] arr) { for (int j = 1; j < arr.length; j++) { int key = arr[j]; //将A[j]插入到已排序的数组A[1...j-1]中 int i = j - 1; while (i >= 0 && arr[i] > key) { arr[i + 1] = arr[i]; i = i - 1; } arr[i + 1] = key; } } public static void main(String[] args) { int[] arr = {6 , 7 , 2 , 5 , 8 , 4 , 1 , 3 , 9}; insertionSort(arr); System.out.println(“插入排序：”); System.out.println(Arrays.toString(arr)); } } |
选择排序算法
内容：
|
第一次遍历找到最小元素 第二次在剩余数组中遍历找到最小元素，即整个数组的次小元素，并按照顺序放在已排列的数列的末尾 ... 第n次在剩余数组中遍历找到第n小元素 |
伪代码：
复杂度分析：
|
时间复杂度为O(n^2)，空间复杂度为O(1)。与插入排序算法相比，选择排序算法的比较次数相同，但交换次数比插入排序算法要少，因此在数据量较大的情况下，选择排序算法的效率要优于插入排序算法。然而，选择排序算法的局限性在于其不稳定，也就是说，在待排序序列中，存在多个元素值相同的元素，在排序后它们在序列中的相对位置可能会发生变化。 |
运行结果：
源代码：
|
public class Sort { //选择排序 public static void selectionSort(int[] arr) { for(int i = 0; i < arr.length - 1 ; i++) { int minindex = i; for(int j = i + 1; j < arr.length; j++) { //如果A[i]大于A[j]，则交换二者的位置 if(arr[minindex] > arr[j]) { minindex = j; } } int temp = arr[i]; arr[i] = arr[minindex]; arr[minindex] = temp; } } public static void main(String[] args) { int[] arr = {6 , 7 , 2 , 5 , 8 , 4 , 1 , 3 , 9}; System.out.println(“选择排序:”); selectionSort(arr); for(int i : arr) { System.out.print(i + “ ”); } } } |
时间复杂度：
递归式分析：
1、递归树法：
2、主定理法：
！！！
eg：
分而治之篇
分而治之：一般步骤 （书73页）
分而治之篇 之 归并排序算法
内容：
|
将待排序的序列划分成若干个子序列，对每个子序列进行排序，然后将已经排好序的子序列合并成一个有序的序列。 核心是通过比较两个有序子序列的首元素，将较小的元素依次放入结果序列中；如果其中一个子序列排完了，直接将另一个子序列剩下的元素并入结果序列。 |
算法流程：
伪代码：
复杂度分析：
|
归并排序是一种稳定的算法，在最坏情况下的时间复杂度为O(nlog n)，但是空间复杂度为O(n)，使用时需要注意空间的限制。它的优势在于适用于序列链表等数据结构以及具有较好的稳定性和复杂度分析。 |
运行结果：
源代码：
|
import java.util.Arrays; public class MergeSort { public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } } |
|
public static void merge(int[] arr, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int[] L = new int[n1]; int[] R = new int[n2]; // L[i] <-- arr[left] R[j] <-- arr[right] 将两个子序列分别赋值给L[i] 和R[j] for (int i = 0; i < n1; i++) { L[i] = arr[left + i]; } for (int j = 0; j < n2; j++) { R[j] = arr[mid + 1 + j]; } // 比较两个有序子序列的首元素，将较小的元素依次放入结果序列中 int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // 如果其中一个子序列排完了，直接将另一个子序列剩下的元素并入结果序列 while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } |
|
public static void main (String[] args) { int[] arr = {6 , 7 , 2 , 5 , 8 , 4 , 1 , 10 , 3 , 9}; mergeSort(arr, 0, arr.length - 1); System.out.println(“归并排序:”); System.out.println(Arrays.toString(arr)); } } |
分而治之篇 之 最大子数组问题
背景：
|
子数组: 子数组为数组X中连续的一段序列 |
内容：
|
最大子数组：在一个数列中找到一个连续子序列，使得该子序列所有数字之和最大。 分而治之法是将数列二分分而治之，找出左半部分、右半部分和跨越中点的三种情况中最大的子数组和。 |
算法流程:
伪代码：
复杂度分析：
|
分治法思路的最大子数组问题时间复杂度为O(nlogn)。因为需要将问题分解成O(logn)个子问题，并且每个子问题的求解需要O(n)的时间。因此总共需要O(nlogn)的时间来解决这个问题。 |
源代码：
|
import java.util.Arrays; public class MaxSubArray { public static int[] maxSubArrayHelper(int[] nums) { return maxSubArray( nums , 0 , nums.length - 1 ); } private static int[] maxSubArray( int[] nums , int low , int high ) { if ( low == high ) { return new int[]{ low , high , nums[low] } ; } else { int mid = ( low + high ) / 2; int[] left = maxSubArray( nums , low , mid ); int[] right = maxSubArray( nums , mid + 1 , high); int[] cross = CrossingSubArray( nums , low , mid , high); int leftSum = left[2]; int rightSum = right[2]; int crossSum = cross[2]; // Smax <-- max{S1,S2,S3} , 求数组nums的最大子数组之和 if ( leftSum >= rightSum && leftSum >= crossSum ) { return left; } else if ( rightSum >= leftSum && rightSum >= crossSum ) { return right; } else { return cross; } } } private static int[] CrossingSubArray( int[] nums , int low , int mid , int high ) { int leftSum = Integer.MIN_VALUE; int Sum = 0; int maxLeft = mid; //从nums[mid]向前遍历求和，并记录最大值leftSum for ( int l = mid ; l >= low ; l-- ) { Sum += nums[l]; if ( leftSum < Sum ) { leftSum = Sum; maxLeft = l; } } |
|
int rightSum = Integer.MIN_VALUE; Sum = 0; int maxRight = mid + 1; //从nums[mid+1]向后遍历求和，并记录最大值rightSum for ( int r = mid + 1 ; r <= high ; r++) { Sum += nums[r]; if ( rightSum < Sum) { rightSum = Sum; maxRight = r; } } return new int[]{ maxLeft , maxRight , leftSum + rightSum }; } public static void main (String[] args) { int[] nums = { -1 , -3 , 3 , 5 , -4 , 3 , 2 , -2 , 3 , 6 }; int[] result = maxSubArrayHelper(nums); System.out.println(“输入的数组为:\n” + Arrays.toString(nums)); System.out.println(“最大子数组中,连续子序列在原始数组中的起始下标、终止下标,以及最大子数组的和为:\n” + Arrays.toString(result)); } } |
分而治之篇 之 快速排序算法
背景:
|
在将原数组一分为二，递归求解子问题时，设计到了“数组划分”思想 |
内容：
|
随机化快速排序(Randomized Quicksort)算法是一种基于“分治”的排序算法，其基本思路是选取一个随机元素(pivot)，将待排序序列分为两个子序列：比pivot小的在左侧，比pivot大的在右侧，然后递归地对两个子序列进行排序，最终将所有子序列合并为一个有序序列。 |
具体流程：
伪代码：
复杂度分析：
|
随机化快速排序的平均时间复杂度为 O(nlogn)，最坏情况下的时间复杂度为 O(n^ 2)，空间复杂度为 O(logn) 或 O(n)。 |
运行结果：
源代码：
|
import java.util.Arrays; import java.util.Random; public class QuickSort { public static int randomizedPartition ( int[] arr , int p , int r ) { int s = new Random().nextInt(r - p + 1) + p; swap( arr , s , r ); int q = partition( arr , p , r ); return q; } public static void randomizedQuickSort( int[] arr , int p , int r ) { if ( p < r ) { int q = randomizedPartition( arr , p , r ); randomizedQuickSort( arr , p , q - 1 ); randomizedQuickSort( arr , q + 1 , r ); } } public static int partition( int[] arr , int p , int r ) { int x = arr[r]; int i = p - 1; for ( int j = p ; j < r ; j++ ) { if ( arr[j] <= x ) { i++; swap( arr , i , j ); } } swap( arr , i +1 , r ); int q = i + 1; return q; } |
|
public static void swap( int[] arr , int i , int j ) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] arr = new int[]{ 9 , 7 , 5 , 11 , 12 , 2 , 14 , 3 , 10 , 6 }; System.out.println(“排序前的数组为:” + Arrays.toString(arr)); randomizedQuickSort(arr , 0 , arr.length - 1 ); System.out.println(“排序后的数组为:” + Arrays.toString(arr)); } } |
分而治之篇 之 汉诺塔问题
内容：（书74页）
|
有三根柱子，标号分别为A、B、C。在A柱子上从下往上按大小顺序依次摆放着 n 个圆盘，现在需要将A柱子上的圆盘移动到C柱子上，每次只能移动一个圆盘，且在移动过程中不能出现大盘放在小盘上面的情况。请问，最少需要移动多少次，才能将所有圆盘从A柱子移动到C柱子上？ |
算法流程：
|
通过三个步骤实现:
|
伪代码：
|
Algorithm Hanoi(n, A, B, C) // 将 A 上面的 n 个圆盘移动到 C 上面，借助 B if n == 1: move(A, C) // 将圆盘从 A 移动到 C else: Hanoi(n-1, A, C, B) // 将 A 上面的 n-1 个圆盘移动到 B 上面，借助 C move(A, C) // 将圆盘从 A 移动到 C Hanoi(n-1, B, A, C) // 将 B 上面的 n-1 个圆盘移动到 C 上面，借助 A |
复杂度分析：
|
汉诺塔问题的递归解法的时间复杂度为 O(2^n)，其中 n 表示圆盘的数量。这是因为，当有 n 个圆盘时，每次移动圆盘时都要将 n-1 个圆盘从一根柱子移动到另一根柱子，而这个操作的时间复杂度是 O(2^(n-1))。 汉诺塔问题的时间复杂度增长非常迅速，随着圆盘数量的增加，所需的步数呈指数级增长。 |
运行结果：
源代码：
|
import java.util.Scanner; public class HanoiTower { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println(“请输入圆盘的数目n:”); int n = sc.nextInt(); // 将A上面的n个圆盘移动到C上面 |
|
String a = “A” , b = “B” , c = “C”; // 三根柱子的标号 System.out.println(“汉诺塔问题运行结果:”); Hanoi(n , a , b , c); } public static void Hanoi(int n , String A , String B , String C) { if (n == 1) { // 将圆盘从A移动到C System.out.println(“move ” + A + “ to ” + C); } else { // 将A上面的n-1个圆盘移动到B上面，借助C Hanoi(n - 1 , A , C , B); // 将圆盘从A移动到C System.out.println(“move ” + A + “ to ” + C); // 将B上面的n-1个圆盘移动到C上面，借助A Hanoi(n - 1 , B , A , C); } } } |
减治：
折半查找：
分治逆序对计数问题：
蛮力法：
分治法优化：
分治次序选择：选第k小元素：
固定位置划分：
随机位置划分：
动态规划篇
最优子问题
一般步骤：（书129页）
动态规划篇 之 0/1背包问题
内容：（书135页）
|
有一个背包，容量为C；有n个物品，每个物品的体积为v[i]，价值为p[i]。要求从这n个物品中选择总体积不超过C的若干个物品放入背包中，使得这些物品的总价值最大。 |
算法流程：
|
用动态规划算法求解。首先，定义二维数组 P[i][c] 表示在前 i 个物品中选出若干个物品放入容量为 c 的背包中所能获得的最大价值。对于每个物品，存在两个选择：放入背包或者不放入背包。因此，可以得到状态转移方程： 如果第 i 个物品的体积 v[i] 大于 c，即装不下，此时 P[i][c] = P[i-1][c] 如果第 i 个物品的体积 v[i] 小于等于 c，可以选择放入或不放入背包： 放入背包：P[i][c] = P[i-1][c-v[i]] + p[i] 不放入背包：P[i][c] = P[i-1][c] |
伪代码：
复杂度分析：
|
动态规划算法解决0/1背包问题的时间复杂度为 O(nC），其中 n 表示物品数量，C 表示背包容量。 |
源代码：
|
import java.util.*; public class KnapsackProblem { // 动态规划实现 0/1 背包问题 // 输入:商品数量n , 各商品的价值p , 各商品的体积v , 背包容量C // 输出:商品价格的最大值，最优解方案 public static int knapsackDP(int n , int[] p , int[] v , int C) { //创建二维数组P[0...n,0...C] 和Rec[0...n,0...C] int[][] P = new int[n+1][C+1]; int[][] Rec = new int[n+1][C+1]; //初始化 for (int i = 0 ; i <= C ; i++) { P[0][i] = 0; } for (int i = 0 ; i <= n ; i++) { P[i][0] = 0; } for (int i = 0 ; i <= C ; i++) { Rec[0][i] = 0; } for (int i = 0 ; i <= n ; i++) { Rec[i][0] = 0; } //求解表格 for (int i = 1 ; i <= n; i++) { for (int c = 1 ; c <= C ; c++) { if (c < v[i - 1]) { P[i][c] = P[i-1][c]; Rec[i][c] = 0; } else { P[i][c] = Math.max(P[i-1][c] , P[i-1][c-v[i-1]] + p[i-1]); Rec[i][c] = 1; } } } //输出最优解方案 int k = C; |
|
//输出最优解方案 int k = C; for (int i = n ; i > 0 ; i--) { if (Rec[i][k] == 1) { System.out.println(“选择第” + i + “个商品”); k = k - v[i-1]; } else { System.out.println(“不选择第” + i + “个商品”); } } return P[n][C]; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println(“请输入商品的数目n:”); int n = sc.nextInt(); int[] v = new int[n]; int[] p = new int[n]; System.out.println(“请依次输入商品的体积v:”); for (int i = 0 ; i < n ; i++) { v[i] = sc.nextInt(); } System.out.println(“请依次输入商品的价值p:”); for (int i = 0 ; i < n ; i++) { p[i] = sc.nextInt(); } System.out.println(“请输入背包的容量C:”); int C = sc.nextInt(); int result = knapsackDP(n , p , v , C); System.out.println(“得到的总价值最大为(即产生的最优解为):” + result); } } |
动态规划篇 之 最大子数组问题
内容：
|
最大子数组：在一个数列中找到一个连续子序列，使得该子序列所有数字之和最大。 |
算法流程：
伪代码：
复杂度分析：
|
动态规划思路的最大子数组问题的时间复杂度为O(n),其中n是数组的长度。因为每个子问题只会被计算一次，所有总共有n个子问题需要计算。 |
|
import java.util.Scanner; public class maxSubArray1 { public static int[] maxSubarraySum(int[] nums, int n) { int[] D = new int[n]; //记录最优解 int[] Rec = new int[n]; //记录终止位置 //初始化 D[n - 1] = nums[n - 1]; Rec[n - 1] = n-1; //动态规划 //自底向上填最优解D和终止位置Rec的表格 //Rec[i]的填写方法:D[i+1] > 0,填入Rec[i+1]的值;D[i+1] < 0,填入i for (int i = n-2 ; i >= 0 ; i--) { if (D[i+1] > 0) { D[i] = nums[i] + D[i+1]; Rec[i] = Rec[i+1]; } else { D[i] = nums[i]; Rec[i] = i; } } //查找解 int maxSum = D[0] , l = 0 , r = 0; for (int i = 1 ; i <= n-1 ; i++) { if (maxSum < D[i]) { maxSum = D[i]; l = i; r = Rec[i]; } } return new int[] { maxSum , l+1 , r+1 }; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("请输入数组的长度n:"); int n = sc.nextInt(); int[] nums = new int[n]; |
|
System.out.println("请依次输入数组的元素:"); for (int i = 0 ; i < n ; i++) { nums[i] = sc.nextInt(); } int[] maxSum = maxSubarraySum(nums, n); System.out.println("最大子数组的和为:" + maxSum[0]); System.out.println("最大子数组的起始位置为:" + maxSum[1]); System.out.println("最大子数组的终止位置为:" + maxSum[2]); } } |
动态规划篇 之 最长公共子序列问题
背景：
|
子序列： 将给定序列中零个或多个元素（如字符）去掉后所得结果 |
内容：
|
最长公共子序列（Longest Common Subsequence，LCS）是指两个序列在某个相同的子序列中所拥有的最长的序列，而子序列不要求在原序列中是连续的。动态规划算法是解决最长公共子序列问题的常见方法。 |
算法流程：
最终构造的递推公式：
伪代码：
复杂度分析：
|
动态规划方法解决最长公共子序列问题的时间复杂度为O(mn)，其中m和n分别为两个序列的长度。 |
运行结果：
源代码：
|
import java.util.*; public class LongestCommonSubsequence { public static char[][] LCS(char[] X, char[] Y, int n, int m) { //创建二维数组C[0...n,0...m]和Rec[0...n,0...m] int[][] C = new int[n + 1][m + 1]; char[][] Rec = new char[n + 1][m + 1]; //初始化 for (int i = 0; i <= n; i++) { C[i][0] = 0; } for (int j = 0; j <= m; j++) { C[0][j] = 0; } //动态规划 用1代替"LU",用2代替"U",用3代替"L"; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (X[i-1] == Y[j-1]) { C[i][j] = C[i - 1][j - 1] + 1; Rec[i][j] = 1; } else if (C[i-1][j] >= C[i][j-1]) { C[i][j] = C[i-1][j]; Rec[i][j] = 2; } else { C[i][j] = C[i][j-1]; Rec[i][j] = 3; } } } System.out.println("最长公共子序列的长度为:" + C[n][m]); return Rec; } public static String getLCS(char[][] Rec, char[] X, int i, int j){ StringBuilder sb = new StringBuilder(); if (i == 0 || j == 0) { System.out.println("没有最长公共子序列"); } |
|
while (i > 0 && j > 0) { if (Rec[i][j] == 1) { i--; j--; sb.append(X[i]); } else if (Rec[i][j] == 2) { i--; } else { j--; } } return sb.reverse().toString(); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("请输入数组X的长度n: "); int n = sc.nextInt(); char[] X = new char[n]; System.out.print("请依次输入数组X的元素:"); // X,测试数据:A B C B D A B for (int i = 0 ; i < n ; i++) { X[i] = sc.next().charAt(0); } System.out.print("请输入数组Y的长度m: "); int m = sc.nextInt(); char[] Y = new char[m]; System.out.print("请依次输入数组Y的元素:"); // Y,测试数据:B D C A B A for (int j = 0 ; j < m ; j++) { Y[j] = sc.next().charAt(0); } char[][] rec = LCS(X, Y, n, m); System.out.print("最长公共子序列为:"); System.out.println(getLCS(rec, X, n, m)); } } |
动态规划篇 之 最长公共子串问题
背景：
内容：
|
给定两个字符串X和Y，求它们的最长公共子串及其长度。 |
算法流程：
伪代码：
复杂度分析：
|
最长公共子串问题的动态规划法的时间复杂度为O(nm)，空间复杂度同样为O(nm)，其中n和m分别为两个字符串的长度。 |
源代码：
|
import java.util.*; public class LongestCommonSubstring { public static int[] longestCommonSubstring(String X, String Y) { int n = X.length() , m = Y.length(); int[][] C = new int[n + 1][m + 1]; int lmax = 0; // 最长公共子串长度 int pmax = 0; // 最长公共子串末尾位置 //初始化 for (int i = 0 ; i < n ; i++) { C[i][0] = 0; } for (int j = 0 ; j < n ; j++) { C[0][j] = 0; } //动态规划 for (int i = 1 ; i <= n ; i++) { for (int j = 1 ; j <= m ; j++) { if (X.charAt(i - 1) == Y.charAt(j - 1)) { C[i][j] = C[i - 1][j - 1] + 1; if (lmax < C[i][j]) { lmax = C[i][j]; pmax = i - 1; } |
|
} else { C[i][j] = 0; } } } return new int[]{lmax , pmax}; } public static void LCS (String X, int lmax, int pmax){ if (lmax == 0) { System.out.println("没有最长公共子串!"); } System.out.print("最长公共子串为:"); for (int i = (pmax - lmax + 1) ; i <= pmax ; i++) { System.out.print(X.charAt(i)); } } public static void main(String[] args) { // 从键盘读入两个字符串 Scanner sc = new Scanner(System.in); System.out.println("请输入字符串X:"); //测试X:ABCADBB String X = sc.next(); System.out.println("请输入字符串Y:"); //测试Y:BCEDBB String Y = sc.next(); // 求解最长公共子串及其长度 int[] result = longestCommonSubstring(X, Y); int lmax = result[0]; int pmax = result[1]; System.out.println("最长公共子串长度为：" + lmax); LCS(X, lmax,pmax); } } |
动态规划篇 之 钢条切割问题
内容：
|
给定一段长度为n的钢条和一个价格表p[1...n] ，求切割钢条的最优方案，使得切割后获得的收益最大。 |
算法流程：
伪代码：
复杂度分析：
|
动态规划法的钢条切割问题的时间复杂度为O(n^2)，空间复杂度为O(n)，其中n为钢条的长度。 |
运行结果：
源代码：
|
import java.util.Scanner; public class RodCutting { public static void rodCutting(int[] p , int n) { int[] C = new int[n+1]; int[] rec = new int[n+1]; // 初始化 C[0] = 0; //动态规划 for (int j = 1 ; j <= n ; j++) { int q = p[j-1]; // 不切割 rec[j] = j; for (int i = 1 ; i <= j - 1 ; i++) { if (q < p[i-1] + C[j-i]) { q = p[i-1] + C[j-i]; rec[j] = i; } } C[j] = q; } System.out.println("最大收益为:" + C[n]); //输出最优方案 System.out.print("切割方案为:{ "); while (n > 0) { System.out.print(rec[n] + " "); n = n - rec[n]; } System.out.print("}"); } |
|
public static void main(String[] args){ Scanner sc = new Scanner(System.in); System.out.print("请输入钢条的长度n:"); //测试: 10 int n = sc.nextInt(); System.out.print("请依次输入钢条价格表p[1...n]:"); //测试: 1 5 8 9 10 17 17 20 24 24 int[] p = new int[n]; for (int i = 0; i < n; i++) { p[i] = sc.nextInt(); } //求最优解 rodCutting(p , n); } } |
动态规划篇 之 矩阵链问题
动态规划篇 之 编辑距离问题
衡量序列的相似程度
贪心算法篇
贪心策略篇 之 部分背包问题
内容：
|
调制饮品比赛: |
算法流程：
伪代码：
复杂度分析：
|
如果为每个物品都计算性价比并按照性价比从大到小排序，需要 O(nlogn) 的时间复杂度。然后，遍历一遍排序后的数组，对每个物品进行选择/放弃（或者选择部分）的操作，这部分的时间复杂度为 O(n)。 因此，总时间复杂度为O(nlogn)+O(n)=O(nlogn)。 |
运行结果：
源代码：
|
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class FractionlKnapsack { // 贪心算法实现 部分背包问题 // 输入:商品数量n , 各商品的价值p , 各商品的体积v , 背包容量C // 输出:商品价格的最大值，最优解方案 private static void knapsack(int n, double[] p, double[] v, int C) { // 计算单位体积价值 double[] indices = new double[n]; for (int i = 0; i < n; i++) { indices[i] = p[i] / v[i]; } |
|
// 按照性价比降序排序 Double[] Ratio = new Double[n]; for (int i = 0; i < n; i++) { Ratio[i] = indices[i]; } Arrays.sort(Ratio, Comparator.reverseOrder()); int i = 0; double ans = 0; // 根据贪心策略求解 while (C > 0 && i < n) { if (v[i] <= C) { System.out.println("选择商品" + (i+1)); ans += p[i]; C -= v[i]; } else { System.out.println("选择" + C + "体积的商品" + (i+1)); ans += p[i] * (C / v[i]); C = 0; } i++; } System.out.print("总价格为:" + ans); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("请输入商品的数目n:"); int n = sc.nextInt(); double[] v = new double[n]; double[] p = new double[n]; System.out.print("请依次输入商品的体积v:"); for (int i = 0; i < n; i++) { v[i] = sc.nextInt(); } System.out.print("请依次输入商品的价值p:"); for (int i = 0; i < n; i++) { p[i] = sc.nextInt(); } System.out.print("请输入背包的容量C:"); int C = sc.nextInt(); knapsack(n, p, v, C); } } |
|
System.out.print("请输入背包的容量C:"); int C = sc.nextInt(); knapsack(n, p, v, C); } } |
动态规划的0/1背包和贪心法的部分背包问题的比较：
贪心策略篇 之 霍夫曼编码问题
内容：
|
对于一个给定的字符集，霍夫曼编码是一种使用变长编码表来将每个字符编码为比特串的方式。编码的长度与字符出现的频率有关，出现频率越高的字符编码长度越短，反之则编码长度越长。 贪心算法可以用来构造霍夫曼编码树，其基本思路是首先将字符出现的频率作为结点的初始权值，然后每次选择两个权值最小的结点并将它们合并为一个新结点，直到所有的结点被合并为一棵树为止。在这个过程中，新结点的权值为它所包含的两个子结点的权值之和。 最终构造出的霍夫曼编码树是一棵无回路的树（也称为无环树），每个叶子结点表示一个字符并给出该字符的编码。 构造出霍夫曼编码树后，可以通过从根结点开始遍历的方式来确定每个字符的编码。遍历左子树时添加一个 “0”，遍历右子树时添加一个 “1”，直到遇到一个叶子结点。对于每个字符，它的编码就是到达它的路径上的比特串。 |
算法流程：
伪代码：
复杂度分析：
|
贪心算法的优点是速度快，时间复杂度为 O(nlogn)，其中 n 是字符集的大小。缺点是它只能得到一个局部最优解，而无法保证一定得到全局最优解。 |
运行结果：
伪代码：
|
import java.util.*; // 记录节点信息 class Node implements Comparable { char c; // 字符 double F; // 出现概率 Node left, right; // 左右子节点 public Node(char c, double F) { this.c = c; this.F = F; } |
|
@Override public int compareTo(Object other) { return Double.compare(this.F, ((Node)other).F); } } public class Huffman { // 数组chars中每个字符出现的概率存放在数组F中，函数返回对应的霍夫曼编码 public static String[] encode(char[] chars, double[] F) { int n = chars.length; // 将char和概率信息保存到Nodes中 Node[] Nodes = new Node[n]; for (int i = 0; i < n; i++) { Nodes[i] = new Node(chars[i], F[i]); } // 构造霍夫曼树 Queue<Node> pq = new PriorityQueue<Node>(); for (int i = 0; i < n; i++) { pq.offer(Nodes[i]); } while (pq.size() > 1) { //弹出两个概率最小的节点 Node left = pq.poll(), right = pq.poll(); // 构造新节点 Node parent = new Node('\0', left.F + right.F); parent.left = left; parent.right = right; pq.offer(parent); } Node root = pq.poll(); // 最后剩下唯一的节点，即霍夫曼树的根 String[] codes = new String[n]; // 保存每个字符的霍夫曼编码 if (n == 1) { codes[0] = "0"; } else { assignCode(root, "", codes); // 从霍夫曼树的根开始递归地生成编码 } return codes; }
|
|
private static void assignCode(Node node, String code, String[] codes) { if (node.c != '\0') { // 叶子节点表示一个字符 codes[node.c - 'a'] = code; } else { // 非叶子节点，递归搜索左右子树 assignCode(node.left, code + "0", codes); assignCode(node.right, code + "1", codes); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("请输入字符个数n:"); int n = sc.nextInt(); char[] chars = new char[n]; double[] F = new double[n]; System.out.print("请依次输入字符:"); for (int i = 0 ; i < n ; i++) { chars[i] = sc.next().charAt(0); } System.out.print("请依次输入各字符频数:"); for (int i = 0 ; i < n ; i++) { F[i] = sc.nextDouble(); } String[] codes = encode(chars, F); for (int i = 0; i < chars.length; i++) { System.out.println(chars[i] + " : " + codes[i]); } } } |
