C++贪心

前言

C++算法与数据结构
打开打包代码的方法兼述单元测试

简介

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。贪心算法的正确性必须证明。常见的证明方法有五种：一，反证法。二，数学归纳法。三，决策包容性。 四，扩展决策范围。五，临项交换。

决策包容性

如果存在最优解，增加某种条件限制后，仍然有最优解。故只需要考虑此种条件下的最优解。

临项交换（微扰）

证明在任意局面下，任何对局部最优策略的微小改变都会造成整体结果变差。经常用于以“排序”为贪心策略的证明。

扩展决策范围（放缩法）

在思考贪心算法时，有时候不容易直接证明局部最优决策的正确性，此时可以往后多扩展一步，进而对当前的决策进行验证。扩展决策范围，即往后多看一步。

数学归纳法

【C++贪心 数学归纳法】1054. 距离相等的条形码|1701

常见场景

中位数贪心：

pos[0…n-1]升序，记录了所有房间的位置，将邮筒放在何处，邮筒到各户的距离最短。
结论：如果n为偶数，则pos[n/2-1]到pos[n/2]之间；如果n为奇数，pos[n/2]。
下面用分组法和扩展决策范围来证明。
先假定n是偶数，分组法：pos[i]和pos[n-1-i]一组，任意一组最小距离为pos[n-1-i]-pos[i]，放在两者的中间，可以取最小值。
当n =2时，放在中间可以取最小值。
当 n=4,放置pos[1]和pos[2]中间可以取最小值。
⋯ \cdots ⋯ 放置到pos[n/2-1]和pos[n/2]可以取最小值。
当n为奇数时：邮箱放到pos[i]，各组取最小值，pos[i]为0。

临项不同

n个字符，能否让相邻的字符不同。
性质一：出现次数最多的字符出现次数<= n/2。则限制队首不为指定字符也可以让相邻不相等。
性质二：n是奇数。出现最多的条形码出现n/2+1次。如果队首可以为此条形码，则可以让相邻不相等。
下面用数学归纳法来证明。
n为1成立：{a}
n为2成立：{a,b},{b,a}
n为3成立：{a,b,a} {a,b,c}{a,c,b}
从小到大证明n = 4 To ∞ \infty ∞
n为偶数：
如果存在两个众数为n/2，将任意众数放到队首，余下的符合性质二。
否则，将任意众数放到队首，余下的符合性质一。
n为奇数：
如果众数为n/2+1，则只有一个众数。否则两个众数的数量为n+1，与n个数矛盾。
将众数放到队首，余下的符合性质一。
从上面的证明过程得知：如果有解，则将众数放到最前面，一定存在解。

反悔贪心

发现无法贪心时，再更改。如：完成第i个任务需要task[i]块砖头或一个梯子。问最多能完成多少个任务，必须依次次完成任务。两种反悔贪心法：一，优先用砖头，砖头不够，就用梯子完成需要砖头最多的任务。二，优先用梯子，梯子不够。将需要砖头最少的梯子换成砖头。

未分类

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。