算法篇--贪心算法

贪心算法

一、算法思想

贪心算法（Greedy Alogorithm）又叫登山算法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但是适用范围有限的策略。

贪心算法没有固定的框架，算法设计的关键是贪婪策略的选择。贪心策略要无后向性，也就是说某状态以后的过程不会影响以前的状态，至于当前状态有关。

贪心算法是对某些求解最优解问题的最简单、最迅速的技术。某些问题的最优解可以通过一系列的最优的选择即贪心选择来达到。但局部最优并不总能获得整体最优解，但通常能获得近似最优解。

在每一步贪心选择中，只考虑当前对自己最有利的选择，而不去考虑在后面看来这种选择是否合理。

贪心算法使用基本步骤：
1.从问题的某个初始解出发
2.采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个不分解，缩小问题的范围或规模。
3.将所有的部分解综合起来，得到问题的最终解。

贪心算法的原理是通过局部最优来达到全局最优，采用的是逐步构造最优解的方法。在每个阶段，都做出一个看上去最优的，决策一旦做出，就不再更改。

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

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

贪心算法很多时候并不能达到全局最优，为什么我们还要使用它呢？

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

该算法存在的问题
1.不能保证求得的最后解是最佳的
2.不能用来求最大值或最小值的问题
3.只能求满足某些约束条件的可行解的范围

二、选择排序

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 int n, i, j, a[2000];
 6 
 7 int main()
 8 {
 9     cin >> n;
10     for (i = 1; i <= n; i++)
11         cin >> a[i];       
12 
13     for (i = 1; i < n; i++)        
14         for (j = i + 1; j <= n; j++)
15             if (a[i] > a[j])        
16                 swap(a[i], a[j]);     
17 
18     for (i = 1; i <= n; i++)
19         cout << a[i] << " ";       
20 
21     return 0;     
22 }

————————————————
原文链接：https://blog.csdn.net/weixin_49370884/article/details/126247776