如何给一个网站做优化,自己做副业可以抢哪个网站,网站后期维护方案,正规网站制作公司有哪些目录 讲解一#xff1a;贪心算法
一、什么是贪心算法#xff1f;
二、贪心算法的应用场景
三、使用Java代码实现贪心算法
四、知识小结
--------------------------------
讲解二#xff1a;动态规划算法
一、什么是动态规划算法
二、动态规划算法求解问题需要具备的…目录 讲解一贪心算法
一、什么是贪心算法
二、贪心算法的应用场景
三、使用Java代码实现贪心算法
四、知识小结
--------------------------------
讲解二动态规划算法
一、什么是动态规划算法
二、动态规划算法求解问题需要具备的基本要素
1. 重复子问题
2. 最优子结构
3. 动态规划算法与分治算法的异同点
4. 动态规划求解的基本步骤
三、列举 7 个常见动态规划算法
1. 数字三角形
1.1. 经典递归解法
1.2. 备忘录法
1.3. 动态规划法
思路一
思路二
2. 最长公共子序列
2.1. 穷举搜索
2.2. 备忘录法
2.3. 动态规划
2.4. 改进
3. 最大子段和
4. 最长公共子串
4.1. 暴力法
4.2. 动态规划
5. 矩阵连乘
6. 最长递增子序列
7. 0-1背包问题 讲解一贪心算法
一、什么是贪心算法
贪心算法是一种思路简单、实现较为容易、效率较高的算法。
它的核心思想是每一步都选择当前局部最优解并且期望通过不断的选择来达到全局最优解。
贪心算法主要分为两个部分选择策略和优化问题。
选择策略指的是每一步如何从多个选项中选择一个局部最优解而优化问题指的是当已经选
择了一个局部最优解后如何把问题规模缩小以便下一步仍然能够找到局部最优解。
二、贪心算法的应用场景
通过上面介绍我们知道贪心算法Greedy Algorithm是一种经典的解题思路它通过每一步
的局部最优解来达到全局最优解的目的。
它通常在数据规模较小且问题有最优子结构的情况下具有较高效率并且与动态规划算法、分
治法等常用算法相比贪心算法的实现较为容易。
它还经常被用来解决优化问题例如
1、集合覆盖问题有一些广播台每个广播台可以覆盖一些地区求出覆盖所有地区需要选择
哪些广播台。
2、背包问题有一个固定大小的背包要尽可能装入最有价值的物品求最大价值量。
3、旅行商问题有一个旅行商需要访问多个城市每个城市之间的距离已知求最短的访问距
离。
4、区间调度问题一个工厂有许多订单需要进行生产每个订单都有一个开始时间和结束时
间求如何排列生产顺序才能完成尽可能多的订单。
三、使用Java代码实现贪心算法
下面我们以背包问题为例来演示如何使用Java代码实现贪心算法。
假设有一个装有可重复使用的商品的背包商品的价值不同重量也不同背包只能装载固定重
量的商品怎样才能使背包中的商品价值最大
我们可以采用择单价最高的商品策略先放入单价最高的商品直到背包无法再容纳下一个商
品再取第二高价值的商品依此类推。
以下是Java代码示例
public class Knapsack {public static double fractionalPack(int capacity, int[] values, int[] weights) {int n values.length;double maxValue 0.0; // 最终最大价值double[] fractions new double[n];// 计算每个商品的单位价值for (int i 0; i n; i) {fractions[i] (double) values[i] / weights[i];}// 按单位价值从高到低排序采用冒泡排序for (int i 0; i n - 1; i) {for (int j i 1; j n; j) {if (fractions[i] fractions[j]) { // 如果i商品的单位价值小于j商品的单位价值则交换double temp fractions[i];fractions[i] fractions[j];fractions[j] temp;//对应的values和weights也需交换temp values[i];values[i] values[j];values[j] (int) temp;temp weights[i];weights[i] weights[j];weights[j] (int) temp;}}}//依次选择单位价值最高的物品for (int i 0; i n; i) {if (weights[i] capacity) {capacity - weights[i];maxValue values[i];} else {maxValue fractions[i] * capacity;break;}}return maxValue;}
}
四、知识小结
贪心算法是一种经典的解题思路在实际应用中很多问题可以用贪心算法求解。Java语言作为
一种广泛应用的编程语言也支持贪心算法的实现。为了能够更好的掌握贪心算法我们需要不
断学习和实践并理解贪心算法的基本思想和应用场景不断提高自己的算法和编程能力。
--------------------------------
讲解二动态规划算法
一、什么是动态规划算法
1动态规划算法与分治法类似其基本思想也是将待求解问题分解成若干个子问题
2经分解得到的子问题往往不是互相独立的有些子问题被重复计算多次
3如果能够保存已解决的子问题的答案而在需要时再找出已求得的答案就可以避免大量
重复计算从而得到多项式时间算法备忘录法
4图解 二、动态规划算法求解问题需要具备的基本要素
1. 重复子问题
递归算法求解问题时每次产生的子问题并不总是新问题有些子问题被反复计算多次这种性质称为子问题的重叠性质动态规划算法对每一个子问题只解一次而后将其解保存在一个表格中当再次需要解此子问题时只是简单地用常数时间查看一下结果通常不同的子问题个数随问题的大小呈多项式增长用动态规划算法只需要多项式时间从而获得较高的解题效率
2. 最优子结构
一个问题的最优解包含着其子问题的最优解这种性质称为最优子结构性质分析问题的最优子结构性质首先假设由问题的最优解导出的子问题的解不是最优的然后再设法说明在这个假设下可构造出比原问题最优解更好的解从而导致矛盾利用问题的最优子结构性质以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解最优子结构是一个问题能用动态规划算法求解的前提
3. 动态规划算法与分治算法的异同点
1动态规划算法与分治法类似其基本思想也是将待求解问题分解成若干个子问题
2分治算法经分解得到的子问题往往是独立的
3动态规划算法经分解得到的子问题往往不是独立的有些子问题被重复计算多次
4. 动态规划求解的基本步骤
1找出最优解的性质并刻划其结构特征
2递归地定义最优值
3以自底向上的方式计算出最优值
4根据计算最优值时得到的信息构造最优解
三、列举 7 个常见动态规划算法
列举 7 个常见动态规划算法练手其余都在刷题篇
1. 数字三角形
有一只小兔子站在一片三角形的胡萝卜地的入口如右图所示图中的数字表示每一个坑中胡萝
卜的数量小兔子每次只能跳到左下角或者右下角的坑中请问小兔子怎么跳才能得到最多数量
的胡萝卜 1.1. 经典递归解法 实现代码
public class Demo {public static void main(String[] args) {int[][] a {{1},{3,2},{4,10,1},{4,3,2,20}};System.out.println(solve(a,0,0));}public static int solve(int[][] a,int i,int j){//第 n1 层结束 》从0层开始计算 那么 i n 时结束if (i a.length){return 0;}return a[i][j] Math.max(solve(a,i1,j),solve(a,i1,j1));}
}
1.2. 备忘录法
详情见文章【算法】备忘录法记忆化搜索上面递归时候我们solve(a,2,1)被重复计算过两次随着层数的增加我们重复计算的子问题也会增加为了避免重复计算子问题我们就需要用到备忘录法就是利用一个二维数组记录每次子问题计算的值每次需要计算子问题时先判断数组中是否计算过保存了有的话直接用数组中结果没有就计算并把结果保存到数组中。代码实现
public class Demo {public static void main(String[] args) {int[][] a {{1},{3,2},{4,10,1},{4,3,2,20}};System.out.println(solve(a,0,0,new int[a.length][a.length]));}public static int solve(int[][] a,int i,int j,int[][] p){//第 n1 层结束 》从0层开始计算 那么 i n 时结束if (i a.length){return 0;}if (p[i][j] 0) {p[i][j] a[i][j] Math.max(solve(a, i 1, j, p), solve(a, i 1, j 1, p));}return p[i][j];}
}
1.3. 动态规划法
思路一
p[i][j]表示(i, j)的达到最后一层的最大路径和那么p[i][j]的最优解包含了子问题p[i1][j]或p[i1][j1]的最优解状态转移方程递归方程 图解 我们最终结果是p[0][0]动态规划法又叫填表法填完上面那张表我们的结果就出来了实现代码
public class Demo {public static void main(String[] args) {int[][] a {{1},{3,2},{4,10,1},{4,3,2,20}};System.out.println(solve(a));}public static int solve(int[][] a){int[][] p a.clone();//最后一层的数不需要修改 从倒数第二次开始for (int i a.length -2; i 0; i--) {for (int j 0; j i; j) {p[i][j] a[i][j] Math.max(p[i1][j],p[i1][j1]);}}return p[0][0];}
}
通过代码可知时间复杂度On N ^ 2
思路二
p[i][j]表示从(1,1)到达(i, j) 的最大路径和那么p[i][j]的最优解包含了子问题p[i-1][j-1]或p[i-1][j]的最优解状态转移方程递归方程思路一就是从表的最后一层开始填思路二是表的第一层开始填
2. 最长公共子序列 2.1. 穷举搜索 2.2. 备忘录法
public class Blog {public static void main(String[] args) {//数组从1开始舍弃0char[] x { ,A,C,D,E,D,C};char[] y { ,A,B,C,D,C};System.out.println(LCS(x, y, x.length-1, y.length-1, new int[x.length][y.length]));}/**** param x 序列X* param y 序列Y* param i X下标* param j Y下标* param c 备忘录表* return 最长子序列的长度*/public static int LCS(char[] x,char[] y,int i,int j,int[][] c){if (i 0||j 0){return 0;}if (c[i][j] 0){if (x[i] y[j]){c[i][j] LCS(x,y,i-1,j-1,c)1;}else {c[i][j] Math.max(LCS(x,y,i-1,j,c),LCS(x,y,i,j-1,c));}}return c[i][j];}} 2.3. 动态规划 public class Blog {//测试public static void main(String[] args) {Scanner scanner new Scanner(System.in);while (scanner.hasNext()){String line1 scanner.nextLine();String line2 scanner.nextLine();char[] chars1 line1.toCharArray();char[] chars2 line2.toCharArray();System.out.println(lcsLength(chars1, chars2));}}public static int lcsLength(char[] x,char[] y){int m x.length;int n y.length;//要填的表int[][] p new int[m1][n1];//表的第1行和第一列全部为0for (int i 0; i m; i) {p[i][0]0;}for (int i 0; i n; i) {p[0][i]0;}for (int i 1; i m; i) {for (int j 1; j n; j) {if (x[i-1]y[j-1]){p[i][j] p[i-1][j-1]1;}else {p[i][j] Math.max(p[i-1][j],p[i][j-1]);}}}return p[m][n];}} package test.gaolang.blog3;import java.util.List;
import java.util.Scanner;/*** author DELLHL*/
public class Blog {//测试public static void main(String[] args) {Scanner scanner new Scanner(System.in);while (scanner.hasNext()){String line1 scanner.nextLine();String line2 scanner.nextLine();char[] chars1 line1.toCharArray();char[] chars2 line2.toCharArray();int[][] b lcsLength(chars1, chars2, new int[chars1.length 1][chars2.length 1]);printlcs(chars1.length ,chars2.length ,chars1,b);System.out.println();}}public static int[][] lcsLength(char[] x,char[] y,int[][] b){int m x.length;int n y.length;int[][] p new int[m1][n1];for (int i 0; i n; i) {p[0][i] 0;}for (int i 0; i m; i) {p[i][0] 0;}for (int i 1; i m; i) {for (int j 1; j n; j) {if (x[i-1]y[j-1]){b[i][j] 1;p[i][j] p[i-1][j-1]1;}else if (p[i-1][j]p[i][j-1]){b[i][j] 2;p[i][j] p[i-1][j];}else {b[i][j] 3;p[i][j] p[i][j-1];}}}return b;}public static void printlcs(int i,int j, char[]a,int [][]drection) {if(i0||j0) {return;}if(drection[i][j]1) {//下面两句代码的位置不能调换调换就相当于逆序输出全部递归完后从第一个开始输出printlcs(i-1,j-1,a,drection);System.out.print(a[i-1]);}else if(drection[i][j]2) {printlcs(i-1,j,a,drection);}else {printlcs(i,j-1,a,drection);}}
} 2.4. 改进 public class Blog {//测试public static void main(String[] args) {Scanner scanner new Scanner(System.in);while (scanner.hasNext()){String line1 scanner.nextLine();String line2 scanner.nextLine();char[] chars1 line1.toCharArray();char[] chars2 line2.toCharArray();System.out.println(lcsLength(chars1, chars2));}}public static int lcsLength(char[] x,char[] y){int m x.length;int n y.length;//要填的表int[][] p new int[2][Math.min(m,n)1];//表的第1行和第一列全部为0for (int i 0; i 1; i) {p[i][0]0;}for (int i 0; i Math.min(m,n); i) {p[0][i]0;}int flag 0;for (int i 1; i Math.max(m,n); i) {flag 1 - flag;for (int j 1; j Math.min(m,n); j) {if (x[i-1]y[j-1]){p[flag][j] p[1-flag][j-1]1;}else {p[flag][j] Math.max(p[1-flag][j],p[flag][j-1]);}}}return p[flag][Math.min(m,n)];}} 3. 最大子段和 public class Test {public static void main(String[] args) {int[] a {-2,11,-4,13,-5,-2};System.out.println(solve(a));}public static int solve(int[] a){int[] p new int[a.length];//以第一个结尾p[0] a[0];int max p[0];for (int i 1; i a.length; i) {//从第二个开始if (p[i-1] 0){p[i] a[i] p[i-1];}else {p[i] a[i];}if (p[i] max){max p[i];}}return max;}
} 4. 最长公共子串
两个字符串输出最长公共子串的长度。
4.1. 暴力法 public class Main {//公共子串public static void main(String[] args) {Scanner scanner new Scanner(System.in);//多组输入测试while (scanner.hasNext()){String line scanner.nextLine();String line2 scanner.nextLine();char[] chars line.toCharArray();char[] chars2 line2.toCharArray();//记录最大长度int max 0;//两个字符串只要有一个为空我们的长度为0直接输出if (chars.length0||chars2.length0){System.out.println(0);}else {//以第一个字符for (int i 0; i chars.length; i) {for (int j 0; j chars2.length; j) {int m i;int k j;int len 0;while(m chars.lengthk chars2.lengthchars[m]chars2[k]){len;m;k;}if (len max){max len;}}}System.out.println(max);}}}
}
4.2. 动态规划 public class Test2 {public static void main(String[] args) {String x acbcbcef;String y abcbced;System.out.println(LCS(x, y));}public static int LCS(String x,String y){char[] a x.toCharArray();char[] b y.toCharArray();int m a.length;int n b.length;int max 0;int[][] p new int[m1][n1];for (int i 0; i m; i) {p[i][0] 0;}for (int i 0; i n; i) {p[0][n] 0;}for (int i 1; i m1; i) {for (int j 1; j n1; j) {if (a[i-1]b[j-1]){p[i][j] p[i-1][j-1]1;if (p[i][j] max){max p[i][j];}}else {p[i][j] 0;}}}return max;}
}
如果要把这个公共子串输出我可以在上面算法的基础上记录一下最大值的横坐标或者纵坐标。
public class Test2 {public static void main(String[] args) {String x acbcbcef;String y abcbced;System.out.println(LCS(x, y));}public static int LCS(String x,String y){char[] a x.toCharArray();char[] b y.toCharArray();int m a.length;int n b.length;int max 0;int index 0;int[][] p new int[m1][n1];for (int i 0; i m; i) {p[i][0] 0;}for (int i 0; i n; i) {p[0][n] 0;}for (int i 1; i m1; i) {for (int j 1; j n1; j) {if (a[i-1]b[j-1]){p[i][j] p[i-1][j-1]1;if (p[i][j] max){max p[i][j];index i;}}else {p[i][j] 0;}}}for (int i max; i 0; i--) {System.out.print(a[index-i]);}System.out.println();return max;}
}
5. 矩阵连乘 动态规划 import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);while (scanner.hasNextInt()){int n scanner.nextInt();int[] a new int[n];for (int i 0; i n; i) {a[i] scanner.nextInt();}System.out.println(matrixChain(a, new int[a.length-1][a.length-1]));}}/*** 矩阵连乘* param p 连乘矩阵* param m 最小解*/public static int matrixChain(int[] p,int[][] m){//矩阵个数int n p.length-1;//ij的情况 m[i][i]:自有一个矩阵没有乘法for (int i 0; i n; i) {m[i][i] 0;}//i j的情况for (int i 1; i n; i) {int k i;for (int j 0; j n-i; j) {//从j分开 m[j][j](0)和m[j1][k] ,合并的乘法次数p[j]xp[j1]与p[j1]xp[k1]m[j][k] m[j1][k] p[j]*p[k1]*p[j1];//m[j][k] 从j1开始分开到k-1结束选出乘法次数最少的for (int l j1; l k; l) {int t m[j][l]m[l1][k] p[j]*p[k1]*p[l1];if (t m[j][k]){m[j][k] t;}}k;}}//m[0][n-1]:第一个矩阵到第n个矩阵连乘的最少次数return m[0][n-1];}
}
import java.util.Scanner;/*** author DELLHL*/
public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);while (scanner.hasNextInt()){int n scanner.nextInt();int[] a new int[n];for (int i 0; i n; i) {a[i] scanner.nextInt();}int[][] ints matrixChain(a, new int[a.length - 1][a.length - 1], new int[a.length - 1][a.length - 1]);
/* for (int i 0; i n-1; i) {for (int j 0; j n-1; j) {System.out.print(ints[i][j]);}System.out.println();}*/traceback(ints,0,n-2);}}/*** 矩阵连乘* param p 连乘矩阵* param m 最小解* param s 记录分割的值*/public static int[][] matrixChain(int[] p,int[][] m,int[][] s){//矩阵个数int n p.length-1;//ij的情况 m[i][i]:自有一个矩阵没有乘法for (int i 0; i n; i) {m[i][i] 0;s[i][i] 0;}//i j的情况for (int i 1; i n; i) {int k i;for (int j 0; j n-i; j) {//从j分开 m[j][j](0)和m[j1][k] ,合并的乘法次数p[j]xp[j1]与p[j1]xp[k1]m[j][k] m[j1][k] p[j]*p[k1]*p[j1];s[j][k] j;//m[j][k] 从j1开始分开到k-1结束for (int l j1; l k; l) {int t m[j][l]m[l1][k] p[j]*p[k1]*p[l1];if (t m[j][k]){m[j][k] t;s[j][k] l;}}k;}}return s;}public static void traceback(int[][] s,int i,int j){//只有一个矩阵 》结束if (i j){return;}//[i,j]是从s[i][j]分开的写成两个部分traceback(s,i,s[i][j]);traceback(s,s[i][j]1,j);//因为我们i是从0开始的所以 i和j输出时都需要加1分开也是从0开始比如s[i][j]i表示分成[i][i]和[i1][j]System.out.println(A[(i1):(s[i][j]1)] * A[(s[i][j]2):(j1)]);}
}
6. 最长递增子序列 import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);//多组测试while (scanner.hasNextInt()){//序列长度int n scanner.nextInt();//序列int[] a new int[n];for (int i 0; i n; i) {a[i] scanner.nextInt();}System.out.println(LIS(a));}}public static int LIS(int[] a){int[] dp new int[a.length];int max 1;for (int i 0; i a.length; i) {//初始化为 1dp[i] 1;//以 i结尾最长递增序列长度for (int j 0; j i; j) {if (a[j] a[i]){if (dp[j] dp[i]){dp[i] dp[j]1;}}}if (dp[i] max){max dp[i];}}return max;}
} import java.util.Scanner;
import java.util.Stack;public class Main3 {public static void main(String[] args) {Scanner scanner new Scanner(System.in);while (scanner.hasNextInt()){int n scanner.nextInt();int[] a new int[n];for (int i 0; i n; i) {a[i] scanner.nextInt();}LIS(a);}}public static int LIS(int[] a){int[] dp new int[a.length];int[] pre new int[a.length];int max_index 1;int max 1;pre[0] -1;for (int i 0; i a.length; i) {dp[i] 1;for (int j 0; j i; j) {if (a[j] a[i]){if (dp[j] dp[i]){dp[i] dp[j]1;pre[i] j;}}}if (dp[i] max){max dp[i];max_index i;}}StackInteger stack new Stack();//递增子序列最长时 最后一个元素为max_indexint index max_index;while (index 0){//入栈stack.push(a[index]);//前一个下标index pre[index];}int size stack.size();for (int i 0; i size; i) {//一一出栈System.out.print(stack.pop() );}System.out.println();return max;}
} 7. 0-1背包问题 public class Knapsack {public static void main(String[] args) {//浪费数组的第一个int[] w {0,2, 2, 6, 5, 4};int[] v {0,6, 3, 5, 4, 6};System.out.println(fun(5, 10, v, w));}public static int fun(int n,int c,int[] v,int[] w){int[][] m new int[n1][c1];//防止数组越界int jMax Math.min(w[n]-1,c);//Step1:填最后一行//jw[n] m[n][j]0for (int j 0; j jMax; j) {m[n][j] 0;}//jw[n] m[n][j]v[n]for (int j w[n]; j c; j) {m[n][j] v[n];}//Step2: 从倒数第二行往前面填for (int i n-1; i 1; i--) {jMax Math.min(w[i]-1,c);for (int j 0; j jMax; j) {m[i][j] m[i1][j];}for (int j w[i]; j c; j) {m[i][j] Math.max(m[i1][j],m[i1][j-w[i]]v[i]);}}//第一行最后一个元素m[1][c] m[2][c];if (c w[1]){m[1][c] Math.max(m[1][c],m[2][c-w[1]]v[1]);}return m[1][c];}
} //根据填的表格推断public static void traceback(int[][] m,int n,int c,int[] w){int[] x new int[n1];for (int i 1; i n; i) {//没有选择if (m[i][c] m[i1][c] ){x[i] 0;}else {x[i] 1;c - w[i];}}x[n] (m[n][c]0) ? 1:0;for (int i 1 ; i x.length; i) {System.out.print(x[i] );}System.out.println();}
