本文共 1666 字，大约阅读时间需要 5 分钟。

目录

一、贪心思想

局部最优推导到全局最优，并且局部最优不影响全局最优。简单来说就是“走一步，看一步”。

这么看来，贪心貌似有些不靠谱。事实上，在某些方面，确实如此。比如：

支付最少纸币数量问题: 一个人从商店购买商品后需要支付M元,现在他有1元、2元、5元的纸币,数量不限,请问怎么支付才能使找出的纸币数量最少?

正常情况下,

        第一步我们先用面值最大的5元的纸币,

        第二步在用面值第二大的2元纸币,

        最后我们才会用最小的1元纸币.

这种解决方案,我们使用的纸币数量最少.

在上面的例子中，我们只从当前步骤最优来考虑，但结果是最优的。

然鹅，在某些时候，局部最优并不能导致全局最优，我们只要在这个例子中改点参数：

例：我们修改纸币面值为1元、2元、4元、5元、6元，现在我们支付9元,如果用贪心法我们得到的结果应该是6+2+1=9元，需要3张纸币，但是最优解其实是5+4元，需要2张纸币就可以了。

那我们该如何判断呢？

二、判断贪心

1.最优子结构性质

 当一个问题的最优解包含其子问题的最优解时,那么我们就称此问题具有最优子结构性质.也就是说,从局部最优可以扩展到全局最优。

2.贪心选择性质

问题的整体最优解可以通过一系列的局部最优的选择来得到。

三、例题

1.陆陆的外卖

题目：

此题就是贪心，因为不管他什么时候开始，只有结束时间决定他什么时候完成，所以只需依次选择结束时间最早的就行

这就是贪心选择性质：

问题的整体最优解可以通过一系列的局部最优的选择来得到。

代码：

2.出租车费

题目：某市出租车计价规则如下：起步4公里10元，即使你的行程没超过4公里；接下来的4公里，每公里2元；之后每公里2.4元。行程的最后一段即使不到1公里，也当作1公里计费。

输入格式:

输入包含多组测试数据。每组输入一个正整数n（n<10000000），表示整个行程的公里数。

当n=0时，输入结束。

输出格式:

对于每组输入，输出最小花费。如果需要的话，保留一位小数。

限制:

空间限制：32MByte

时间限制：1秒

样例:

输入：

3

9

16

0

输出：

10

20.4

36

这题需要做个计算：

起步4公里10元，那么每公里就是2.5元。而接下来的4公里，必须要经过起步4公里。所以起步的8公里，就是2.4元。之后每公里2.4元。

所以：

起步4公里：每公里2.5元。

接下来的4公里：每公里2元。

起步8公里：每公里2.4元。

8公里之后：每公里2.4元。

因为起步8公里和8公里之后都一样，所以不用管他，但起步4公里是最贵的，所以我们应尽量避免

代码：

#include
   
    double n,sum;double pd(int x){	if(x<=4) return 10; 	if(x<=8) return 10+(x-4)*2;	if(x<=12) return 18+(x-8)*2.4;	return 0;}int main() {	while(scanf("%lf",&n)!=EOF) {		sum=0;		if(n==0) return 0;		while(n>12){			n-=8.0;			sum+=18.0;		}		sum+=pd(n);		if(sum!=(int)sum) printf("%.1lf\n",sum); 		else printf("%d\n",(int)sum); 	}}
   

总结

贪心算法没有固定的框架，关键是如何选择贪心策略，且必须具备无后效性，只与当前状态有关。

虽然贪心法不一定能得到最优解，但是他思路简单，编程容易。因此，如果一个问题确定用贪心法可以得到最优解，那么我们应该尽量使用贪心法来解决。

转载地址：https://blog.csdn.net/jhfhfhu/article/details/119933537 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！