关于贪心算法，ChatGPT是这么定义的：

贪心算法（Greedy Algorithm）是一种求解最优化问题的算法范式，它在每一步选择当前状态下的最优解，最终期望通过一系列的最优选择达到全局最优解。贪心算法通常适用于那些具有最优子结构性质的问题，其中整体问题的最优解可以通过局部子问题的最优解得到。

贪心算法的一般思想是按照某种规则，从问题的初始状态开始，通过一系列局部最优的选择，逐步逼近问题的全局最优解。每一步的选择不依赖于前面的选择，也不会影响以后的选择。因此，贪心算法通常是一个非常高效的算法，因为它不需要考虑所有可能的解决方案，只需关注当前的最优选择。

显然，此算法是通过局部运算达到计算整体最优解的效果。

举个生活中常见的实例：

假设有1元、2元、5元、10元、20元、50元、100元的纸币。现在要用这些钱来支付，至少要用多少张纸币？用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的

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
#include<stdio.h>

int main() {
    int m[7]= {1,2,5,10,20,50,100}; //先有纸币的数额
	int ret;
	//所找的金额
	int num;          //所需纸币的张数
    while((	scanf("%d",&ret))!=EOF) {
		while(ret>0) {
			if(ret>=100) {
                ret-=100;
			} else if(ret>=50&&ret<100) {
                ret-=50;
			} else if(ret>=20&&ret<50) {
                ret-=20;
			} else if(ret>=5&&ret<20) {
                ret-=5;
			} else if(ret>=2&&ret<5) {
                ret-=2;
			} else if(ret>=1&&ret<2) {
                ret-=1;
			}
			num++;
		}
		printf("%d\n",num);
	}
}

贪心算法的基本思路

  1. 候选集合S
    为了构造问题的解决方案，有一个候选集合C作为问题的可能解，问题的最终解均取自于候选集合C。
  2. 解集合S
    随着贪心选择的进行，解集合不断扩展，直到构成一个满足问题的完整解。
  3. 解决函数solution
    检查解集合是否构成问题的完整解。
  4. 选择函数select
    即贪心策略，这是贪心算法的关键，它指出哪个候选对象有希望构成成问题的解。
  5. 可行函数feasible
    检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。

对应的，

该算法存在的问题

  • 不能保证求得的最后解是最佳的

  • 不能用来求最大值或最小值的问题

  • 只能求满足某些约束条件的可行解的范围

要选出最优解不是一件容易的事，要证明局部最优为全局最优，要进行数学证明，否则就不能说明为全局最优。

很多问题表面上看来用贪心算法可以找到最优解，实际上却把最优解给漏掉了。这就像现实生活中的“贪小便宜吃大亏”。所以在解决问题的时候，一定要谨慎使用此算法，一定要注意这个问题适不适合采用贪心算法。

但是在很多大规模问题中，寻找最优解是一件相当费时耗力的事情，有时候付出大量人力物力财力后，回报并不与投入成正比。在这个时候选择相对最优的贪心算法就比较经济可行了。有的问题对最优的要求不是很高，在充分衡量付出和回报后，选择贪心算法未尝不是一种不错的选择。