安徽省建设厅官方网站进不去,韩国u17出线,江苏建设装饰集团有限公司,东莞网站建设总部地址贪心算法#xff08;几种常规样例#xff09;
贪心算法#xff0c;指在对问题进行求解的时候#xff0c;总是做出当前看来是最好的选择。也就是说不从整体上最优上考虑#xff0c;算法得到的结果是某种意义上的局部最优解 文章目录贪心算法#xff08;几种常规样例…贪心算法几种常规样例
贪心算法指在对问题进行求解的时候总是做出当前看来是最好的选择。也就是说不从整体上最优上考虑算法得到的结果是某种意义上的局部最优解
文章目录贪心算法几种常规样例介绍使用步骤模板贪心算法的缺陷经典例子常见例子活动选择问题钱币找零问题背包问题小船过河问题区域覆盖介绍
可以用贪心算法解决的问题有以下特征 1.贪心选择的性质一个问题的整体最优解可以通过一系列局部的最优解的选择达到。并且每一次的选择可以依赖于之前做出的选择但是不依赖后面做出的选择。这就是贪心选择性质。对于一个具体的问题要确定他是否具有贪心选择的性质必须证明每一步所作的贪心选择最终导致问题的整体的最优解 2.最优子结构性质当一个恩问题的最优解包含其子问题的最优解的时候此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法的求解所在。
使用步骤
使用贪心算法的基本步骤 1建立数学模型来描述问题 。 2把求解的问题分成若干个子问题 。 3对每个子问题求解得到子问题的局部最优解。 4把子问题的解局部最优解合成原来解问题的一个解。
实际上在使用贪心算法的时候待选
模板
while(约束条件成立)
{选择当前最优解记录并累计到最后的解中if(当前最优解使用完毕)当前最优解当前次优解
}贪心算法的缺陷
以下缺陷
1.不能保证解是最佳的。因为贪心算法得到的是局部最优解不是从整体开了整体最优解。
2.贪心算法只能确定某些问题的可行性范围 缺陷1和2的意思是贪心算法是有局限性的就i比如钱币找零如果是8元有2元和5元那么5元一张2元一张剩下1元那么接下来就无法运算了实际上可以四张2元即可这就是一个例子 3.贪心算法一般用来解决最大或者最小解 该缺陷就是贪心算法是以某一种策略来选择一个数值而不是遍历出所有解要遍历出某个问题的所有解的话常常使用回溯法 经典例子 1.活动选择问题 2.钱币找零问题 3.再论背包问题 4.小船过河问题 5.区间覆盖问题 常见例子
活动选择问题 该问题一般可以用贪心算法和动态规划来解决我们下文用贪心算法来解决。 问题的形式为在某地要举办多个活动每一个活动要花费不同的时间起止时间不同问怎么安排尽量多的活动呢该问题用贪心算法可以解决的原因是下个活动的选择可以只是取决于上一个活动的截止时间不必要考虑全局 活动1234567891011开始时间130535688212结束时间4567891011121314在解决这个问题的时候要对于结束时间进行排序因为上一个活动的结束时间会影响下一个活动的选择而当前活动的开始时间不会影响下一个活动的选择所以只看结束时间就好用上一个活动的结束时间来跟下一活动的开始时间进行对比如果前者小于后者那么就是后者就是下一个活动否则继续比较下下一个活动的开始时间 解题思路
将所有活动按照结束时间进行排序然后默认选取第一个活动用变量endTime标注当前活动的结束时间然后与后面活动的开始时间进行比较如果前者结束时间小于等于后者活动开始时间那么选择后者这个活动反之继续比较下下一个活动再次进行判断重复进行第三步直到所有活动比较完成
import java.util.*;/*** 活动选择* 大概形式为在某一个地方有多个活动要进行活动有开始时间和结束时间我们该如何选择才能在这一天中这一个地点举办最多的活动* 求解最多的活动个数为*/
class Play{int preTime;int endTime;//表示活动的开始时间和结束时间
}
public class 活动选择 {public static void main(String[] args) {Scanner scannernew Scanner(System.in);//我们可以用容器来存储各个活动然后进行贪心算法最后得到结果//我们可以用链表来进行存储,排序LinkedListPlay linkedListnew LinkedList();int nscanner.nextInt();//表示活动的个数for (int i 0; i n ; i) {//提案写每一个活动的开始时间和结束时间Play playnew Play();play.preTimescanner.nextInt();play.endTimescanner.nextInt();linkedList.add(play);//存储链表中然后进行对于结束时间排序}Collections.sort(linkedList, new ComparatorPlay() {Overridepublic int compare(Play o1, Play o2) {return o1.endTime-o2.endTime;}});//排序完成//然后进行判别从第一个活动开始int num0;//计数Play TimelinkedList.get(0);for (int i 0; i linkedList.size() ; i) {if(Time.endTimelinkedList.get(i).preTime){TimelinkedList.get(i);num;}}System.out.println(num);//得到}
}
钱币找零问题 该问题的一般描述是假设1元、2元、5元、10元、20元、50元、100元的纸币分别有a , b , c , d , e ,f 张。现在要用这些钱来支付K元至少要用多少张纸币该问题和上个问题有些类似要解决该问题时一般也有两个数组一个表示面额的大小一个表示不同面额钱币对应的数量并且表示面额的数组是有序的。 我们求解的是最少的钱币数目所以可以使用贪心算法
1.理所当然先使用大额纸币当大额纸币张数不够的时候再使用后面较小面额的纸币依次递减直到表示完所有纸币
2.做题方法可以递归也可以迭代
import java.util.*;public class 钱币找零问题 {public static void main(String[] args) {//题目指定币值和相应的数量用最少的数量去凑齐某金额//思路利用贪心算法我们优先选择面值大的纸币依次类推直到凑齐总金额Scanner scannernew Scanner(System.in);int numscanner.nextInt();//输入总金额greedy(num);}public static void greedy(int num){int[] values { 1, 2, 5, 10, 20, 50, 100 };//数量int[] counts { 3, 3, 2, 1, 1, 3, 3 };//获取需要各种面值多少张int[] result getNumber(num, values, counts);System.out.println(各币值的数量Arrays.toString(result));}public static int[] getNumber(int sum,int []values,int[]counts){int []resultnew int[7];//表示有七种钱币//我们要找的是每一种钱币所需的票数int add0;//表示需要的总钱数for (int i values.length-1; i 0 ; i--) {int num(sum-add)/values[i];if(numcounts[i]){numcounts[i];}//add加上数值addaddnum*values[i];result[i]num;}return result;}//或者这样迭代public static int[] get(int sum,int []values,int[]counts){int []resultnew int[values.length];for (int i values.length-1; i 0 ; i) {int numMath.min(counts[i],sum/values[i]);result[i]num;sumsum-num*values[i];}return result;}
}背包问题
不是01背包
常见题型为给定n种物品一个背包背包的容量是c二米一个物品i的价值为vi重量为wi如何选择装入的物品使得背包的总价值最大 此处的背包问题指的是部分背包不是像01背包问题那样某个物品不能拆开此处的物品可以拆开选取一部分放入背包中。从贪心算法的角度来看我们保证的是背包的总价值最大就是要确保放入的每一件物品的单个价值尽量大。可以拆开 步骤如下
1.需要将物品按照单位重量价值进行排序。
2.将尽可能多的单位i重量价值最高的物品装入被阿波若最大单位重量价值的物品全部装入背包后背包华友多余容量则选择单位重量价值次高的尽可能多的装入背包中。
3.如果最后一件物品无法装入那就计算可以装入的比例然后按照比例装入
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Scanner;/*** 贪心的背包 有n个物品一个背包然后想使得这个背包的价值最大* 不是01背包不可拆分物品这个是可以拆分的*/
class beiBao{int values;int weight;//价值和重量double wValues;//单个物品的单位重量的价值
}
public class 背包 {public static void main(String[] args) {Scanner scannernew Scanner(System.in);int nscanner.nextInt();int weightscanner.nextInt();//背包能承受的重量LinkedListbeiBao linkedListnew LinkedList();for (int i 0; i n ; i) {beiBao bnew beiBao();b.valuesscanner.nextInt();b.weightscanner.nextInt();b.wValuesb.values/b.weight;linkedList.add(b);}Collections.sort(linkedList, new ComparatorbeiBao() {Overridepublic int compare(beiBao o1, beiBao o2) {return (int)(o2.wValues-o1.wValues);}});for (int i 0; i n ; i) {System.out.println(linkedList.get(i).wValues);}double allvalues0;boolean[] flagnew boolean[n];for (int i 0; i flag.length; i) {flag[i]false;//表示没有放入背包中}for (int i 0; i n ; i) {if(linkedList.get(i).weightweight){flag[i]true;weightweight-linkedList.get(i).weight;allvalueslinkedList.get(i).values;System.out.println(重量为linkedList.get(i).weight价格为linkedList.get(i).values可以完全装入);}}for (int i 0; i n ; i) {if(!flag[i]){double rate(double)weight/linkedList.get(i).weight;allvaluesallvaluesrate*linkedList.get(i).values;weight-linkedList.get(i).weight;System.out.println(重量为linkedList.get(i).weight价值为linkedList.get(i).values装入比例为rate);}}System.out.println(总价值为allvalues);}
}小船过河问题 该问题常见的描述是有n个人需要过河只有一艘船最多能乘坐两个人串的航行速度为两人中较慢的一人的速度过去后需要一个人把船划回来把n个人运到对岸最少需要多久。 假设这些人花费的时间都存储在一个数组中升序排列也就是由快到慢每个人所花费的时间为time[0],time[1]……time[n] 当人数4的时候该问题有两个选择 1.最快的和次快的先过河然后最快的将船划回来次慢的和最慢的过河然后次快的回来此时我们计算以下这个过程花费的时间 图示 第二种方式 1.最快的最慢的过河然后最快的将船划回来最快的和次慢的过河然后最快的再回来 图示 上面过河有两种方式具体使用的时候可以比较谁时间更短再使用他 如果人数小于4 1.人数为三的时候此时固定用时为time[0]time[1]time[2] 2.人数为二的时候此时固定用时为time[1] 3.人数为一的时候固定用时为time[0] /** 有n个人需要过河只有一艘船最多能乘2人船的运行速度为2人中较慢一人的速度* 过去后还需一个人把船划回来把n个人运到对岸最少需要多久。*/
public class River {public static void main(String[] args) {int[] times{1,2,4,5,8};int resultcrossRiver(times);System.out.println(所花时间为result);}private static int crossRiver(int[] times){/*n表示还未过河的人数初始化为所有人*/int ntimes.length;int result0;while(n0){if(n1){resultresulttimes[0];break;}else if(n2){resultresulttimes[0]times[1];break;}else if(n3){resultresulttimes[0]times[1]times[2];break;}else{/*在每次过河时在两种方式上进行比较选择耗时更少的那个*/resultresultMath.min(times[1]times[0]times[n-1]times[1],times[n-1]times[0]times[n-2]times[0]);/*无论采取哪种方式最后的结果都是讲最慢的和次慢的运送过河也就是数组的最后两位所以此处可简单地将数组长度-2*/nn-2;}}return result;}
}区域覆盖 此问题描述的是给定一个长度为m的区间再给出n条线段的起点和终点闭区间求最少使用读哦少条线段 可以将整个区间完全覆盖步骤如下 在所有待选择的区间里剔除起点和终点在所求范围之外的区间。将所有区间按起点进行排序默认选中第一个点然后在挑选点的过程中需要遵循以下原则新区间的起点要小于当前区间的终点新区间的终点应大于当前区间的起点循环重复步骤3直到当前区间的终点值预期的终点值结束寻找区间的过程 import java.util.*;
class quJian{int pre;int end;//表示区间的起点和终点
}
public class 区间覆盖 {public static void main(String[] args) {Scanner scannernew Scanner(System.in);//加入区间 10个int nscanner.nextInt();int mscanner.nextInt();//假设所求区间范围为[n,m]LinkedList quJianlinkedListnew LinkedList();for (int i 0; i 7 ; i) {quJian qjnew quJian();qj.prescanner.nextInt();qj.endscanner.nextInt(); //1.删除起点和终点在所要求范围外的区间if(!(qj.prenqj.endn||qj.premqj.endm)){linkedList.add(qj);}}//先进行排序Collections.sort(linkedList, new ComparatorquJian() {Overridepublic int compare(quJian o1, quJian o2) {return o1.pre-o2.pre;//按照小区间的起点排下序升序}});//然后进行选取boolean flagfalse;int count1;//计数System.out.println(起点linkedList.get(0).pre,linkedList.get(0).end);int endlinkedList.get(0).end;for (int i 1; i linkedList.size() ; i) {if(linkedList.get(i).preendlinkedList.get(i).endend){endlinkedList.get(i).end;//更新end点for (int j i1; j linkedList.size() ; j) {//然后从这后面找到最长的endif(linkedList.get(j).endend){endlinkedList.get(j).end;count;//找到一个区间System.out.println(linkedList.get(j).pre linkedList.get(j).end);if(endm){flagtrue;}}}}if(flag){break;}}System.out.println(count);}
}
