动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果 [1] 。 [2]
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 [1] 。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择 [1] 。
第一题：给定硬币的面值种类 * ，每种硬币的个数是不固定的，要支付的金额也是不固定的 * 找钱问题 1 5 10 50 100 排序 * 最少来看 大头 * 500 100 100 10 10 5 500 500 500 500 100 100 100 10 10 10 10 1
package 第八章动态规划和贪心算法; import java.util.Random; import java.util.Scanner; public class Demo1 { /** * 给定硬币的面值种类 * ，每种硬币的个数是不固定的，要支付的金额也是不固定的 * 找钱问题 1 5 10 50 100 排序 * 最少来看 大头 * 500 100 100 10 10 5 * 500 500 500 500 100 100 100 10 10 10 10 1 * * 1 硬币的 每种面值的数量 我不知道 * 2 支付的金额我不知道 * 3 支付金额我也不知道 * @param args */ public int[] coins= {1,5,10,50,100,500}; //coins // 设定数组 用于随机存放生成每种硬币的个数 public int[] nums= new int [coins.length]; private void init() { for (int i = 0; i < coins.length; i++) { int s=new Random().nextInt(10); //生成个数硬币个数 nums[i]=s; System.out.println("面值"+coins[i]+"硬币的数量"+nums[i]+"个"); } System.out.println("请输入要支付的金额:"); Scanner scanner=new Scanner(System.in); int money=scanner.nextInt(); scanner.close(); int num=print(money, coins.length-1); System.out.println("最少硬币个数为:"+num); } /** * * @param money 要支付的 1212 * @param index 对应下标 5 * @return */ private int print(int money,int index) { if(money==0 ||index==0) return money; // 当剩余要支付的钱大于一元硬币所有个数，那说明找不开 if(money>0&&index==0) { if(money>nums[index]) { } } // 根据下标获得当前硬币的面值 int curMoney=coins[index];//500 //获得需要的个数量 int x=money/curMoney; // 当前硬币有多少个 int y=nums[index]; //不管是需要个数大于拥有的个数还是小于 总是小于那个 int min=Math.min(x, y); //总钱数-个数*当前的 int other=money-min*coins[index]; System.out.println("需要面值为:"+coins[index]+"的硬币个数为:"+min); // 调用方法 return min+print(other, index-1); } public static void main(String[] args) { new Demo1().init(); } }
渡河问题：
package 第八章动态规划和贪心算法; import java.util.Arrays; import java.util.Random; import java.util.Scanner; public class Demo2 { private void init() { System.out.println("输入渡河的人数:"); Scanner scanne = new Scanner(System.in); int n = scanne.nextInt(); scanne.close(); // 保存每一个人的渡河时间 int[] times = new int[n]; for (int i = 0; i < times.length; i++) { times[i] = new Random().nextInt(10) + 1; } System.out.println("排序前:"); System.out.println(Arrays.toString(times)); // 随机生成的时间是乱序的，肯定需要对每一个人的渡河时间进行排序 Arrays.sort(times);// 升序排列，从小到大 System.out.println("排序后:"); System.out.println(Arrays.toString(times)); print(n, times); } /** * * @param n * 渡河的总人数 * @param times * 每一个人的渡河时间 */ private void print(int n, int[] times) { // 渡河人数一直减少 int person = n; // 耗费的渡河的总时间 int sum = 0; while (person > 0) { // 总人数一个人 if (person == 1) { sum += times[0]; break; } else if (person == 2) { sum += times[1]; break; } else if (person == 3) { sum += times[1] + times[0] + times[2]; break; } else { // 3个人以上的分两种情况考虑 // 第一种: 1,4出发 1回来 1,3过去 1回来 int s1 = times[person - 1] + times[0] + times[person - 2] + times[0]; // 第二种:1,2过去，1回来，3,4过去，2回来， int s2 = times[1] + times[0] + times[person - 1] + times[1]; // 因为两种情况不确定每一个人的渡河时间，所有不知道那种方式是最少的时间 int min = Math.min(s1, s2); person -= 2; sum+=min; } } System.out.println("渡河花费的最少时间为:"+sum+"秒"); } public static void main(String[] args) { new Demo2().init(); } }
6个学生按年龄排序。
package 第八章动态规划和贪心算法; import java.util.Arrays; import java.util.Random; /** * 6个学生按年龄排序 * @author MZFAITHDREAM *对象排序 */ public class Demo3 { public static void main(String[] args) { // TODO Auto-generated method stub Student[] students=new Student[6]; for (int i = 0; i < students.length; i++) { students[i]=new Student("张"+i,new Random().nextInt(10)+20, "江西省"); System.out.println(students[i]); } Arrays.sort(students); System.out.println("排序后==================================================="); for (int i = 0; i < students.length; i++) { System.out.println(students[i]); } } }
package 第八章动态规划和贪心算法; /** * 比较对象 * @author MZFAITHDREAM * */ public class Student implements Comparable<Student>{ private String name; private int age; private String address; public Student() { super(); // TODO Auto-generated constructor stub } public Student(String name, int age, String address) { super(); this.name = name; this.age = age; this.address = address; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public String getAddress() { return address; } public void setAddress(String address) { this.address = address; } @Override public String toString() { return "Student [name=" + name + ", age=" + age + ", address=" + address + "]"; } /** * */ // + 从小到大 // - 从大到小 @Override public int compareTo(Student o) { int a=this.age-o.getAge(); // return 0; return a*-1; } }
区间调度问题
package 第八章动态规划和贪心算法; import java.util.Arrays; import java.util.Random; import java.util.Scanner; /** * 区间调度问题 * @author Administrator * */ public class Demo4 { private void init() { System.out.println("输入工作的数量:"); Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); scanner.close(); //定义数组，存储所有工作的开始时间 int[] start=new int[n]; //定义数组，存储所有工作的结束时间 int[] end=new int[n]; // 金钱 随机生成 int [] many =new int[n]; //定义工作的数组，将每一份工作的开始时间和结束时间封装到一起 Job[] jobs=new Job[n]; for (int i = 0; i < n; i++) { //随机生成每一份工作的开始时间和结束时间 //【1,10】 start[i]=new Random().nextInt(10)+1; end[i]=new Random().nextInt(10)+1+start[i]; jobs[i]=new Job(start[i], end[i]); // 随机生成many many[i]=new Random().nextInt(10)+1; } //将随机生成的乱序时间的工作进行从小到大排序 Arrays.sort(jobs); for (int i = 0; i < jobs.length; i++) { System.out.println(jobs[i].toString(i)); } print(jobs); } //定义方法，把排好序的所有工作进行挨个比较 //以结束时间最早的工作作为第一份工作， //第二份工作的开始时间一定在第一份工作的结束时间之后 private void print(Job[] jobs) { //定义变量，用于记录最多能做多少份工作 int max=1; //获得第一份工作的结束时间 int end=jobs[0].getEtime(); for (int i = 0; i < jobs.length; i++) { //判断前一份工作的结束时间是否小于后一份工作的开始时间 if (end<jobs[i].getStime()) { max++; end=jobs[i].getEtime(); } } System.out.println("最多能做"+max+"份工作"); } public static void main(String[] args) { new Demo4().init(); } } //工作，开始时间和结束时间 class Job implements Comparable<Job>{ private int stime;//开始时间 private int etime;//结束时间 public int getStime() { return stime; } public void setStime(int stime) { this.stime = stime; } public int getEtime() { return etime; } public void setEtime(int etime) { this.etime = etime; } public Job(int stime, int etime) { super(); this.stime = stime; this.etime = etime; } public Job() { super(); } public String toString(int index) { return "第【"+index+"】工作的开始时间是"+stime+",结束时间是"+etime; } @Override public int compareTo(Job o) { //先按照结束时间进行从小到大排序 int x=this.etime-o.etime; if (x==0) { //说明比较的两份工作的结束时间相同，将这两份工作按开始时间进行从小到大排列 return this.stime-o.stime; }else { return x; } } }
package 第八章动态规划和贪心算法; import java.util.Random; import java.util.Scanner; /** * @author MZFAITHDREAM * 定义三个数组 * 理解思路 * 创建scanner 用户 输入 一条字符串 *第一个数组 随机打印 字母内容 并且排序 *第二个数组 进行 将数组 A 倒序排列 *第三个数组 将前两个数组进行比较 依次排序 * @param args */ public class Demo5 { // private void init() { System.out.println("输入生成的字符串的长度"); Scanner scanner =new Scanner(System.in); int n=scanner.nextInt(); scanner.close(); StringBuilder builder=new StringBuilder(); for (int i = 0; i < n; i++) { // A Z char a=(char) ((char)new Random().nextInt(26)+65); builder.append(a); } System.out.println("生成字符串为:"+builder.toString()); print(builder.toString()); } private void print(String s) { // 字符串倒叙排列 倒叙排列 String s1=new StringBuilder(s).reverse().toString(); System.out.println("倒叙字符串为:"+s1); int lenght=s.length(); //创建空的内存 StringBuilder builder =new StringBuilder(); // 循环比较 while(builder.length()<lenght) { // 整个字符串进行比较 if(s.compareTo(s1)<=0) { // s<s1 // 取出数字 char c=s.charAt(0); // 放入数字 builder.append(c); s=s.substring(1); // 否则 }else { // 从倒叙取出第一个字符 char c1=s1.charAt(0); // 放入数字 builder.append(c1); s1=s.substring(1); } } System.out.println("排序后字符串为"+builder.toString()); } public static void main(String[] args) { // TODO Auto-generated method stub /** * @author MZFAITHDREAM * 调用方法 */ new Demo5().init(); // System.out.println((int)'A'); // StringBuilder builder=new StringBuilder("abc"); // builder.append("1234"); // System.out.println(builder); } }
背包问题
package 第八章动态规划和贪心算法; import java.util.Arrays; import java.util.Iterator; import java.util.Random; import java.util.Scanner; /** * 背包问题 * 重量不知道 * 物品不知道 * @author MZFAITHDREAM * */ public class Demo6 { private void init() { System.out.println("输入物品的数量:"); Scanner scanner =new Scanner(System.in); int n=scanner.nextInt(); //重量为 int [] weight=new int[n]; for (int i = 0; i < weight.length; i++) { weight[i]=new Random().nextInt(10)+1; } System.out.println("输入背包的总重量"); int max=scanner.nextInt(); // 排序 Arrays.sort(weight); System.out.println(Arrays.toString(weight)); print(weight, max); } private void print(int[]ws,int max) { int num=0; int sum=0; // 循环遍历 for (int i = 0; i < ws.length; i++) { sum+=ws[i]; // 判断当前背包总重量 if(sum<=max) { num++; }else { System.out.println("不能再放"); break; } } System.out.println("该背包能装物品数量"+num); } public static void main(String[] args) { // TODO Auto-generated method stub new Demo6().init(); } }
体重不同
package 第八章动态规划和贪心算法; import java.util.Arrays; import java.util.Random; import java.util.Scanner; /** * * @author MZFAITHDREAM * *体重不同 */ public class Demo7 { private void intit() { System.out.println("请输入渡河人数"); Scanner scanner = new Scanner(System.in); int n=scanner.nextInt(); int[] weights=new int[n]; for (int i = 0; i < weights.length; i++) { weights[i]=new Random().nextInt(10)+1; } Arrays.sort(weights); System.out.println(Arrays.toString(weights)); System.out.println("输入船的MAX重量"); int max=scanner.nextInt(); scanner.close(); // 定义变量 用于统计剩余多少人 int person=n; int boat=0; // 定义下标 的开始 与结束 int p1=0; int p2=n-1; while(person>0) { // 体重不贵超过 两个人一起运走 if(weights[p1]+weights[p2]>max) { boat++; person--; p2--; }else { boat++; person-=2; p1++; p2--; } } System.out.println("需要最少"+boat); } public static void main(String[] args) { new Demo7().intit(); } }
算法在于自己的实践，在于时间的积累。是一个漫长的过程。我们备战蓝桥杯一个多月的时间，我了解到了只是基础真正的算法高手都在练习算法，因为算法真的能让你的大脑思维提升。这只是我训练的八章成果。算法的在于你要有计算机语言去执行你要实现的功能。面向对象的思维思考问题。
