C++算法之贪心算法

贪心算法是一种求解最优解问题的算法，它的核心思想是每一步都采取当前状态下最优的选择，从而最终得到全局最优解。它是C++重要的一种算法。下面会介绍贪心算法。

目录

1.步骤

1.2 例

2.框架

3.例题

3.1 删数问题

13

 3.2 接水问题

1.步骤

（1）确定问题的最优子结构：问题的最优子结构指的是原问题的最优解可以通过其子问题的最优解得到。这一步通常需要根据问题的特性进行分析。

（2）制定贪心策略：贪心策略是贪心算法的核心，它指的是每一步的最优选择方式。贪心策略通常需要满足贪心选择性质，即每一步的最优选择不依赖于之前所做的选择。

（3）实现贪心策略：贪心策略的实现通常涉及到对问题的数据结构和算法的选择，例如贪心策略是基于数值大小的，那么需要使用合适的数据结构（例如优先队列）来存储和获取当前状态下的最优选择。

（4）分析算法的正确性：贪心算法的正确性通常需要通过数学证明来证明它的贪心选择性质以及最终得到的解一定是全局最优解。

（5）分析算法的复杂度：贪心算法的复杂度通常取决于贪心策略的实现以及问题的特性。

需要注意的是：贪心算法只能用在局部最优解能导致全局最优解的问题上。

1.2 例

下面以一个例子来详解贪心算法的应用过程：

有一些区间，在这些区间中选择尽可能多的不重叠的区间。 

步骤：

1. 确定问题的最优子结构：这个问题具有最优子结构，即在原问题中，如果我们知道了前n个区间的最优解，则可以构造出前n+1个区间的最优解。

2. 制定贪心策略：对于每一次选择最优区间，我们选择区间结束时间最早的一个。

3. 实现贪心策略：我们可以使用优先队列来存储区间，并根据结束时间来排序，然后依次选择结束时间最早的区间。

4. 分析算法的正确性：我们可以通过反证法来证明该贪心策略是正确的。假设存在一个最优解，其中包含了不止一个结束时间比当前选择的区间早的区间，那么我们可以将其中一个区间换成当前选择的区间，得到的解一定不会更劣，因为当前选择的区间是在所有结束时间比它早的区间中，结束时间最早的一个。

5. 分析算法的复杂度：由于需要将区间按照结束时间排序，因此时间复杂度为O(nlogn)。

2.框架

从问题的某一初始解出发;
while(能朝给定总目标前进一步)
{
    利用可行的决策，求出可行解的一个解元素;
}
由所有解元素组成成问题的一个可行解;

3.例题

3.1 删数问题

删数问题(Noip1994)

【题目描述】

输入一个高精度的正整数n，去掉其中任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。

输出新的正整数。（n不超过240位）

输入数据均不需判错。

【输入】

n

s

【输出】

最后剩下的最小数。

【输入样例】

175438

4

【输出样例】

13

#include
using namespace std;
#define N 300
int main()
{
    int k, an = 0; 
    char s[N], a[N];
    cin >> s >> k;
    int len = strlen(s), i, ct = 0;
    for(i = 0; i  0 && a[an] > s[i] && ct s[i]时，删除a[an]
        {
            an--;
            ct++;//删除数字个数加1
        }
        a[++an] = s[i];//无论如何s[i]都会填充进数组a
    }
    while(ct  m;
    for(int i = 1; i > w[i];
    for(int i = 1; i