- 1SnowNLP和jieba库实现中文分词_中文分词可以用jieba和snownlp
- 2算法设计与分析（贪心法）_贪心算法的基本思想
- 3数据结构-----栈（栈的初始化、建立、入栈、出栈、遍历、清空等操作）
- 4升级openai库导致的404错误排查记录
- 5微软Bing GPT支持AI绘画了，输入文字就能出图_gpt绘图
- 6数学建模--非整数规划求解的Python实现_非线性整数规划求解python
- 7【chatgpt】归一化前训练测试集拆分还是归一化后训练测试集拆分
- 8使用PX4+T265+Jetson Nano实现无人机室内定点飞行（问题集）_飞控定点模式失效
- 9微信小程序消息订阅功能_微信小程序订阅功能
- 10matlab语言的由来与发展历程_matlab 应用的发展史
五大算法思想（二）贪心算法及常见例子_贪心算法几个经典例子
赞
踩
一、理论基础
贪心算法，指在对问题求解时，总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑，算法得到的结果是在某种意义上的局部最优解。
1.1 适用场景
可以用贪心算法解决的问题一般有如下特征：
1>贪心选择性质。一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
2>最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。
1.2 使用步骤
使用贪心算法的基本步骤：
1>建立数学模型来描述问题 。
2>把求解的问题分成若干个子问题 。
3>对每个子问题求解，得到子问题的局部最优解。
4>把子问题的解局部最优解合成原来解问题的一个解。
以上都是官方说法。依个人的理解，在贪心选择性质里，其实隐含着一个条件，就是：在使用贪心算法时，待选择的因素是有序的。在该前提下，才可能做出对当前最优的选择。用公式来表示的话，大致如下：
while(约束条件成立){
选择当前最优解，记录并累积到最后的解中
if(当前最优解使用完毕)
当前最优解 = 当前次优解
}
1.3 算法缺陷
贪心算法也存在如下缺陷：
1>不能保证解是最佳的。因为贪心算法总是求的局部最优解，并未从整体考虑整体最优解。
2>贪心算法只能确定某些问题的可行性范围。
缺陷1和缺陷2表示的意思是类似的，就是贪心算法是有局限性的。此处以一个例子来说明：比如钱币找零问题，假如有15元，需要用11、5、1三种面额的钱币来表示，如果用贪心算法来选择的话，会从11开始选择，这样就会选出11+1+1+1+1的方案，用5张钱币来表示，但实际上，用5+5+5的方案，使用的钱币更少，此时贪心方案就选不出全局最优解。
3>贪心算法一般用来解决求最大或最小解。
该缺陷也好理解，贪心算法是以某种策略选择一个值，而不是遍历出所有解，要遍历出某个问题所有解的话，常常用的是回溯法。
1.4 经典例子
常见例子如下：
1>活动选择问题
2>钱币找零问题
3>再论背包问题
4>小船过河问题
5>区间覆盖问题
接下来将对这些例子进行实现，来探究贪心算法思想的具体使用方法。
二、常见例子
2.1 活动选择问题
该问题是一般可以用贪心算法和动态规划两种方法解决，此篇文章主要介绍贪心算法实现方式。该类问题的形式一般如下：在某个地方需要举办不同的活动，每个活动要花费不同时间（起止时间不同），问怎样安排，可以安排尽量多的活动？此问题之所以可以用贪心算法解决，是因为下个活动的选择可以只取决于上个活动结束时间，而不必从全局考虑。
我们假设有个已经按结束时间排好序的活动列表，开始时间和结束时间如下：
| 活动 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 开始时间 | 1 | 3 | 0 | 5 | 3 | 5 | 6 | 8 | 8 | 2 | 12 |
| 结束时间 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
在解决该问题时，需要先对每个活动按结束时间进行排序。也许有人会问，为什么要对活动的结束时间，而不是开始时间进行排序，这样做的原因是当前活动的结束时间会影响到下一个活动的选择，而当前活动的开始时间不会影响下一个活动的选择。
整个的解题思路，大致如下：先把活动按结束时间排序，然后默认选取第一个活动，用变量来标识当前活动的结束日期，作为选择下一个活动的日期的判断标准，具体标准为：下一个选取的活动的开始时间要>=当前活动的结束时间。然后重复此过程，直到遍历完整个数组。
活动选择问题的迭代解法，示例代码如下：
private static List<Integer> activityChoice(int[] startTime, int[] endTime){ List<Integer> list = new ArrayList<Integer>(); /*因为活动已经按结束时间进行过升序排列，所以要默认选中第一个活动*/ list.add(0); /*当前开始活动的结束时间*/ int curTime = endTime[0]; for(int i=1;i<endTime.length;i++){ /*如果目前的活动的开始时间>=之前选择的活动的结束时间，则选取该活动，更新当前时间*/ if (startTime[i]>=curTime) { list.add(i); curTime = endTime[i]; } } return list; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
活动选择问题的递归解法，示例代码如下：
static List<Integer> acivitySelector(int[] startTime, int[] endTime, int i, int n,List<Integer> list) { /*因为活动已经按结束时间进行过升序排列，所以要默认选中第一个活动，+1是因为数组下标从0开始，此处是数组下标+1*/ if(i==0){ list.add(i+1); } int j=i+1; /*此处的循环是过滤掉不符合要求的活动*/ while (j<=n && endTime[i]>startTime[j]){ j++; } //找到一个满足f[i]<=s[j]的活动，添加到list if (j<=n) { /*j+1对应活动的编号，也就是数组下标+1*/ list.add(j+1); /*更新一下当前活动j，然后继续向后找满足条件的活动*/ acivitySelector(startTime, endTime, j, n,list); } return list; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
完整代码示例如下：
package Greedy; import java.util.ArrayList; import java.util.List; /*贪心算法，活动选择问题*/ public class ChooseActivity { public static void main(String[] args) { int[] startTime = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12}; int[] endTime = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }; /*迭代解法*/ List<Integer> activityTime=activityChoice(startTime,endTime); for (Integer activity: activityTime) System.out.print(activity+1+" "); System.out.println(); /*递归解法*/ List<Integer> activityTime2 = new ArrayList<Integer>(); activityTime2=acivitySelector(startTime,endTime,0,startTime.length-1,activityTime2); for (Integer activity: activityTime2) System.out.print(activity+" "); } /*活动选择问题的迭代解法*/ private static List<Integer> activityChoice(int[] startTime, int[] endTime){ List<Integer> list = new ArrayList<Integer>(); /*因为活动已经按结束时间进行过升序排列，所以要默认选中第一个活动*/ list.add(0); /*当前开始活动的结束时间*/ int curTime = endTime[0]; for(int i=1;i<endTime.length;i++){ /*如果目前的活动的开始时间>=之前选择的活动的结束时间，则选取该活动，更新当前时间*/ if (startTime[i]>=curTime) { list.add(i); curTime = endTime[i]; } } return list; } /*活动选择问题的递归解法*/ static List<Integer> acivitySelector(int[] startTime, int[] endTime, int i, int n,List<Integer> list) { /*因为活动已经按结束时间进行过升序排列，所以要默认选中第一个活动，+1是因为数组下标从0开始，此处是数组下标+1*/ if(i==0){ list.add(i+1); } int j=i+1; /*此处的循环是过滤掉不符合要求的活动*/ while (j<=n && endTime[i]>startTime[j]){ j++; } //找到一个满足f[i]<=s[j]的活动，添加到list if (j<=n) { /*j+1对应活动的编号，也就是数组下标+1*/ list.add(j+1); /*更新一下当前活动j，然后继续向后找满足条件的活动*/ acivitySelector(startTime, endTime, j, n,list); } return list; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
测试结果：
1 4 8 11
1 4 8 11
2.2 钱币找零问题
该问题的一般描述是：假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？该问题和上个问题有些类似，要解决该问题时，一般也有两个数组，一个表示面额的大小，一个表示不同面额钱币对应的数量，并且表示面额的数组是有序的。
由于该题目求的是最少的纸币数，所以理所应当要先使用大额纸币，然后依次递减，用较小额的纸币，直到表示完所有钱币。所以该题的解决思路是：优先使用大额钱币，待大额钱币使用完后，再使用次大额的钱币，直到完全表示了K元。同样，该问题也有迭代和递归两种解法。
迭代解法的示例代码如下：
private static int[] countMoney(int[] values,int[] counts,int money){
/*结果数组，用来存放每种面额对应的钱币的数量*/
int[] result=new int[values.length];
/*先用大额钱币，所以从后向前遍历values数组*/
for(int i=values.length-1;i>=0;i--){
/*使用当前面额钱币时，用到的数量*/
int num=Math.min(counts[i],money/values[i]);
/*将结果存储到结果数组*/
result[i]=num;
/*钱币总额需要减掉已表示的钱币额度*/
money=money-num*values[i];
}
return result;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
递归解法的示例代码如下：
/*钱币找零问题的递归解法*/
private static void countMoney2(int[] values,int[] counts,int money,int position,int[] result){
if(money>0){
int num=Math.min(counts[position],money/values[position]);
result[position]=num;
countMoney2(values,counts,money-num*values[position],position-1,result);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
完整代码示例如下：
package Greedy; /* * 假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, * c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？ */ public class Coin { public static void main(String[] args) { /*人民币面额集合*/ int[] values = {1,2,5,10,20,50,100}; /*各种面额对应数量集合*/ int[] counts = {3,1,2,1,1,3,5}; /*结果数组，用来存放每种面额对应的钱币的数量*/ int[] result = countMoney(values,counts,365); for(int i=0;i<result.length;i++){ /*当对应面额的钱币数量为0时，没必要打印*/ if(result[i]!=0) System.out.println("需要用面额"+values[i]+"元的钱币"+result[i]+"张"); } int[] result2= new int[values.length]; countMoney2(values,counts,365,values.length-1,result2); for(int i=0;i<result2.length;i++){ if(result2[i]!=0) System.out.println("需要用面额"+values[i]+"元的钱币"+result2[i]+"张"); } } /*钱币找零问题的迭代解法*/ private static int[] countMoney(int[] values,int[] counts,int money){ /*结果数组，用来存放每种面额对应的钱币的数量*/ int[] result=new int[values.length]; /*先用大额钱币，所以从后向前遍历values数组*/ for(int i=values.length-1;i>=0;i--){ /*使用当前面额钱币时，用到的数量*/ int num=Math.min(counts[i],money/values[i]); /*将结果存储到结果数组*/ result[i]=num; /*钱币总额需要减掉已表示的钱币额度*/ money=money-num*values[i]; } return result; } /*钱币找零问题的递归解法*/ private static void countMoney2(int[] values,int[] counts,int money,int position,int[] result){ if(money>0){ int num=Math.min(counts[position],money/values[position]); result[position]=num; countMoney2(values,counts,money-num*values[position],position-1,result); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
测试结果：
需要用面额5元的钱币1张
需要用面额10元的钱币1张
需要用面额50元的钱币1张
需要用面额100元的钱币3张
需要用面额5元的钱币1张
需要用面额10元的钱币1张
需要用面额50元的钱币1张
需要用面额100元的钱币3张
2.3 背包问题
此问题常见的描述是：给定n种物品，1个背包，背包容量为c,每个物品i的价值为vi，重量为wi，如何选择装入物品能使背包的总价值最大？此处的背包问题指的是部分背包，不是像0-1背包问题中的某个物品不能拆开，此处的物品可以拆开，选取一部分放入背包中。
从贪心算法的角度看， 要保证背包中的物品总价值最大，就是要确保放入的每件物品的单个价值尽量大。也就是说，步骤如下：
1>需要将物品按照单位重量价值进行排序。
2>将尽可能多的单位重量价值最高的物品装入背包，若最大单位重量价值的物品全部装入背包后，背包还有多余容量，则选择单位重量价值次高的并尽可能多地装入背包。
3>如果最后一件物品无法全部装入，则计算可以装入的比例，然后按比例装入。
此处用迭代方式实现，示例代码如下：
package Greedy; /* * 给定n种物品，1个背包，背包容量为c,每个物品i的价值为vi，重量为wi，如何选择装入物品能使背包的总价值最大？ */ public class Package { public static void main(String[] args) { /*每件物品的重量*/ int[] weights={10,30,20}; /*每件物品的价值*/ int[] values={60,120,100}; /*背包的容量限制*/ int packNum=50; maxPackageValue(weights,values,packNum); } private static void maxPackageValue(int[] weights,int[] values,int packNum){ /*单位重量价值比*/ double[] univalent=new double[values.length]; /*最后背包中存储的总价值*/ double allValue=0.0; for(int i=0;i<univalent.length;i++){ univalent[i]=(double)values[i]/weights[i]; } /*1.使用冒泡排序，按单位价值进行升序排序*/ for(int i=0;i<univalent.length-1;i++){ for(int j=0;j<univalent.length-1-i;j++){ if(univalent[j]>univalent[j+1]){ /*对单位价值排序*/ double temp=univalent[j]; univalent[j]=univalent[j+1]; univalent[j+1]=temp; /*对wights排序*/ int tempWeight=weights[j]; weights[j]=weights[j+1]; weights[j+1]=tempWeight; /*对values排序*/ int tempValue=values[j]; values[j]=values[j+1]; values[j+1]=tempValue; } } } /*此数组用来表示每种物品是否已经被放入背包*/ int[] packFlag=new int[univalent.length]; for(int i=0;i<packFlag.length;i++){ /*代表还没放入背包*/ packFlag[i]=0; } /*2.将可以完整存放的物品装入背包*/ for(int i=univalent.length-1;i>=0;i--){ /*代表可以装的下*/ if(weights[i]<packNum){ packNum=packNum-weights[i]; packFlag[i]=1; allValue=allValue+values[i]; System.out.println("重量为:"+weights[i]+"，价值为："+values[i]+"的物品可以被完全装入"); } } for(int i=0;i<packFlag.length;i++){ /*3.该物品不能被完全放入背包，需要放入部分*/ if(packFlag[i]==0){ /*该物品可以放入的比例*/ double rate=(double)packNum/weights[i]; allValue=allValue+values[i]*rate; System.out.println("重量为:"+weights[i]+"，价值为："+values[i]+"的物品可以被装入的比例是："+rate); } } System.out.println("背包中可以存放的总价值是："+allValue); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
测试结果：
重量为:10，价值为：60的物品可以被完全装入
重量为:20，价值为：100的物品可以被完全装入
重量为:30，价值为：120的物品可以被装入的比例是：0.6666666666666666
背包中可以存放的总价值是：240.0
2.4 小船过河问题
该问题的常见描述是：有n个人需要过河，只有一艘船，最多能乘2人，船的运行速度为2人中较慢一人的速度，过去后还需一个人把船划回来，把n个人运到对岸，最少需要多久。
假设这些人所花费的时间都存储在一个数组time中，升序排列，也就是由快到慢，每个人所花费的时间为time[0],time[1]…time[n-2],time[n-1]。
在人数>=4时，该问题的解决思路常常有两种：
1>最快的和次快的过河，然后最快的将船划回来；次慢的和最慢的过河，然后次快的将船划回来。此时我们可以计算一下这个过程所花费的时间（至于为什么要计算这个过程所花费的时间，因为当人数>=4时，一直将这个过程重复下去即可），过程如下：
从上图看出，该类方式所花费时间为：time[0]+2time[1]+time[n-1]。
2>最快的和最慢的过河，然后最快的将船划回来，最快的和次慢的过河，然后最快的将船划回来。过程如下：
从上图看出，该类方式所花费时间为：2time[0]+time[n-2]+time[n-1]。
上面讨论了当过河的人大于等于四个人的情况。每次送两个人过河的方式共有两种，在具体使用时可以比较一下用哪种方式比较快，再决定使用的方式。接下来还要看一下过河时人数小于等于三个的情况：
1>当过河人数为三个时，此固定用时time[0]+time[1]+time[2]。
2>当过河人数为二个时，也许有人会问过河人数为三时，不是包含了这个情况吗？确实是包含了，此处指的初始的人数就是两个，固定用时time[1]。
3>当过河人数为一个时，固定用时time[0]。
接下来就是代码实现，示例代码如下：
package Greedy; /* * 有n个人需要过河，只有一艘船，最多能乘2人，船的运行速度为2人中较慢一人的速度， * 过去后还需一个人把船划回来，把n个人运到对岸，最少需要多久。 */ public class River { public static void main(String[] args) { int[] times={1,2,4,5,8}; int result=crossRiver(times); System.out.println("所花时间为："+result); } private static int crossRiver(int[] times){ /*n表示还未过河的人数，初始化为所有人*/ int n=times.length; int result=0; while(n>0){ if(n==1){ result=result+times[0]; break; }else if(n==2){ result=result+times[0]+times[1]; break; }else if(n==3){ result=result+times[0]+times[1]+times[2]; break; }else{ /*在每次过河时，在两种方式上进行比较，选择耗时更少的那个*/ result=result+Math.min(times[1]+times[0]+times[n-1]+times[1],times[n-1]+times[0]+times[n-2]+times[0]); /*无论采取哪种方式，最后的结果都是讲最慢的和次慢的运送过河，也就是数组的最后两位，所以此处可简单地将数组长度-2*/ n=n-2; } } return result; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
测试结果：
所花时间为：20
2.5 区间覆盖问题
此问题的描述是：给定一个长度为m的区间，再给出n条线段的起点和终点（闭区间），求最少使用多少条线段可以将整个区间完全覆盖。要解此题的完整步骤如下：
1>在所有待选择的区间里，剔除起点和终点在所求范围之外的区间。
2>将所有区间按起点进行排序。
3>默认选中第一个点，然后在挑选点的过程中，需要遵循以下原则：1、新区间的起点要小于等于当前区间的终点；2、新区间的终点要大于当前区间的起点。
4>循环重复步骤3，直到当前区间的终点值>=预期的终点值，结束寻找区间的过程。
此处省略步骤1，重点关注后3步，示例代码如下：
package Greedy; /* * 数轴上有n个闭区间[ai, bi]，选择尽量少的区间覆盖一条指定线段[s, t]。 */ public class CoverSection { public static void main(String[] args) { int[][] ections={{1,4},{2,4},{2,6},{3,5},{3,6},{3,7},{6,8}}; /*此处假设的是求[1,8区间，所需的最少区间数，因为起点是从1开始的， * 所以1不作为参数传入，只将终点值8作为参数传入即可]*/ int count =overSection(ections,8); System.out.println("最少需要"+count+"个区间"); } private static int overSection(int[][] ections,int length){ /*默认选中第一个*/ int count=1; System.out.println(ections[0][0]+","+ections[0][1]); /*初始化终点，默认为第一个区间的终点*/ int end=ections[0][1]; boolean stopFlag=false; for(int i=1; i<ections.length; i++){ /*要挑出的新区间，条件有2个： *1、开头要小于等于上一个挑选的区间的终点 *2、终点要大于上一个挑选的区间的终点*/ if(ections[i][0]<=end && ections[i][1]>end){ /*终点更新为当前区间的终点*/ end=ections[i][1]; for(int j=i+1;j<ections.length;j++){ /*在开头满足条件时，终点选最大的那个*/ if(ections[j][1]>end){ /*更新终点，元素个数+1*/ end=ections[j][1]; count++; System.out.println(ections[j][0]+","+ections[j][1]); /*如果当前区间>=length，代表可以结束循环*/ if(end>=length){ stopFlag=true; } } } } /*结束循环*/ if(stopFlag) break; } return count; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
测试结果：
1,4
3,7
6,8
最少需要3个区间
