贪心策略

dsy2022 · 2023-07-31 16:13:34 · 个人记录

贪心策略

云剪贴板获取源码效果更好

文章目录：

       1. 引言
       2. 贪心策略的基本原理
       3. 贪心策略的适用性
       4. 经典案例：找零问题
       5. 贪心的优缺点及应用范围
       6. 例题讲解
       7. 结论

1. 引言

在计算机科学与算法设计领域，贪心算法（Greedy Algorithm）是一种高效且广泛应用的策略，通常用于解决优化问题。贪心算法的核心理念在于每一步都采取局部最优解，寄希望通过局部最优选择的组合来达到全局最优解。虽然贪心算法并不是解决所有问题的银弹，但在许多场景下，它展现出了出色的性能和效率。

2. 贪心策略的基本原理

当谈论贪心策略的基本原理时，我们要明确它的核心思想：每一步都选择当前的最优解，寄希望通过局部最优选择的组合来达到全局最优解。贪心算法通常适用于那些具有最优子结构和贪心选择性质的问题。

文章目录：

       1. 最优子结构（Optimal Substructure）
       2. 贪心选择性质（Greedy Choice Property）
       3. 局限性

1. 最优子结构（Optimal Substructure）：

贪心算法适用于问题的解决过程可以被切分为一系列子问题，并且每个子问题的最优解能够组合成原问题的最优解。这意味着问题可以通过一系列局部最优解的组合，来得到全局最优解。在每个子问题上应用贪心策略，能够保证每一步的选择都是局部最优的。

举例说明：假设有一个图需要从顶点A走到顶点 B，每条边上都有一个权重（表示代价或距离），我们要找到一条从 A 到 B 的最短路径。这个问题具有最优子结构，因为如果我们在某个中间顶点 C 处得到了一条从 A 到 C 的最短路径和一条从 C 到 B 的最短路径，那么连接这两条路径将得到一条从 A 到 B 的最短路径。

2. 贪心选择性质（Greedy Choice Property）：

贪心选择性质是贪心算法的关键特征。它指的是每一步都选择当前状态下的局部最优解，而不管这个选择是否会影响到未来步骤的解决方案。贪心选择性质确保了我们在每一步都做出看似最佳的决策，从而积累起来得到整体上的最优解。

举例说明：考虑背包问题，假设有一个背包容量为 W，有一系列物品，每个物品有自己的价值和重量。我们要选择哪些物品放入背包，以便在不超过背包容量的前提下，获得最大的总价值。贪心选择性质在这里体现为每次优先选择单位重量价值最高的物品放入背包。虽然这个策略并不一定能得到全局最优解，但它是贪心算法的核心特性。

3. 局限性：

尽管贪心算法在某些问题上表现出色，但它并非解决所有问题的通用方法，因为贪心算法缺乏对未来影响的预测能力。由于每一步的选择都依赖于当前局部最优解，并不考虑其它可能的选择，贪心算法可能会陷入局部最优解而无法找到全局最优解。

3. 贪心策略的适用性

当谈论贪心策略的适用性时，我们需要了解在哪些情况下贪心算法表现出色。贪心算法在解决问题时，通常满足以下条件，使其能够得到有效的近似最优解：

文章目录：

       1. 前向性（Forward Thinking）
       2. 子问题最优性（Optimal Substructure）
       3. 贪心选择性质（Greedy Choice Property）

1. 前向性（Forward Thinking）:

贪心算法适用于问题的解决过程可以被切分为一系列可独立处理的步骤。每个步骤都只依赖于当前的局部状态，而不受未来步骤的影响。这种前向性使得贪心算法能够通过局部最优选择的组合，逐步达到全局最优解。

举例说明：在旅行商问题（TSP）中，旅行商需要访问一系列城市，并返回起始城市，使得总的旅行距离最短。贪心算法可以逐步选择离当前城市最近的未访问城市，直到所有城市都被访问一次，然后返回起始城市。这里每一步都是局部最优解，最终获得近似的全局最优解。

2. 子问题最优性（Optimal Substructure）:

贪心算法适用于问题具有最优子结构的情况，即问题的最优解可以由子问题的最优解构成。这样，我们可以通过贪心选择的方式，逐步解决子问题，并保证每一步选择都是局部最优的。

举例说明：在霍夫曼编码中，贪心算法用于构建最优的变长编码。这里的子问题最优性体现在构建树的过程中，每次选择出现频率最低的两个节点，然后合并成一个新节点，并更新频率。这样，每一步的选择都是局部最优的，最终得到整体上的最优编码。

3. 贪心选择性质（Greedy Choice Property）:

贪心算法在每一步都选择当前状态下的局部最优解，而不管这个选择是否会影响到未来步骤的解决方案。贪心选择性质确保了我们在每一步都做出看似最佳的决策，从而积累起来得到整体上的最优解。

举例说明：在最小生成树（MST）问题中，贪心算法（如 Prim 算法和 Kruskal 算法）分别从单个顶点和单个边开始，并逐步选择连接到当前集合的最小权重的顶点或边。这种贪心选择性质确保了每一步都是局部最优解，最终生成最小生成树。

4. 经典案例：找零问题

文章目录：

       1. 背景
       2. 目标
       3. 解决方案
       4. 适用性

1. 背景:

找零问题是在货币交易中常见的一个问题。假设你是一位收银员，你需要找零给顾客一个特定的金额。现在你手上有一定面值的钞票，你需要选择如何组合这些钞票，以最少的张数找零给顾客，同时确保找零的金额不超过顾客需要的金额。

2. 目标:

在找零问题中，我们的目标是以最少的钞票张数找零，确保不超过所需的找零金额。这样，不仅可以减少钞票的使用量，还能提高交易效率。

3. 解决方案:

贪心算法是解决找零问题的有效方法。其基本思想是每次选择当前面值最大的钞票进行找零，直到找零的金额为 0。贪心选择的策略是尽量多地使用大面值的钞票，这样可以最大限度地减少钞票的张数。

举例说明：

假设你手上有面值为 1 美元、5 美元、10 美元和 20 美元的钞票。现在顾客需要找零 28 美元。

第一步：由于面值为 20 美元的钞票是最大面值，选择一张 20 美元的钞票找零，剩余找零金额为 8 美元。

第二步：由于面值为 5 美元的钞票是次大面值，选择一张 5 美元的钞票找零，剩余找零金额为 3 美元。

第三步：由于面值为 1 美元的钞票是最小面值，选择 3 张 1 美元的钞票找零，剩余找零金额为 0 美元。

至此，完成了找零过程。总共使用了 1 张 20 美元钞票、1 张 5 美元钞票和 3 张 1 美元钞票，共计 5 张钞票。这是一个找零问题的近似最优解。

4. 适用性：

找零问题符合贪心选择性质和最优子结构的条件。每次选择当前面值最大的钞票进行找零，确保每一步都是局部最优的，同时问题的最优解可以由子问题的最优解构成。因此，贪心算法在找零问题上表现出色，能够高效地得到近似的全局最优解。

然而，需要注意的是，并非所有的找零问题都适合贪心算法。例如，如果手上的面值不是标准的货币面值（如 1、5、10、20 美元），而是一组任意的面值，贪心算法可能无法得到最优解。因此，在实际应用中，我们需要仔细考虑问题的特性，确认贪心算法的适用性，以获得令人满意的解决方案。

5. 贪心的优缺点及应用范围

文章目录：

       1. 优点
       2. 缺点
       3. 应用范围

1. 优点

文章目录：

       1. 简单高效
       2. 容易实现
       3. 可用于近似解
       4. 适用于大规模问题

• 简单高效

贪心算法的设计思想相对简单，执行过程直观易懂。它通常是一种直接的贪心选择策略，每一步都选择当前状态下的局部最优解。由于贪心算法不进行回溯和全局优化，算法的实现相对轻量，从而降低了算法的复杂性。

• 容易实现

贪心算法的简单性使得它易于实现。一般情况下，我们只需要找到问题中的贪心选择性质，并采用迭代的方式逐步得到解决方案。相较于其他复杂的算法设计方法，贪心算法更容易编写和调试，节省了开发时间。

• 可用于近似解

尽管贪心算法不能保证一定能得到全局最优解，但在某些情况下，它能够提供接近全局最优解的近似解。对于那些难以用传统的动态规划等算法得到精确解的问题，贪心算法可以作为一种有效的替代方案，为实际应用提供快速可行的解决方案。

• 适用于大规模问题

贪心算法通常时间复杂度较低，执行效率高。由于它只关注当前局部最优解，不进行全局搜索和回溯，因此在处理大规模问题时表现优异。这使得贪心算法在实际应用中可以处理大量数据和复杂情况，同时保持较快的运行速度。

2. 缺点

文章目录：

       1. 不能保证全局最优解
       2. 缺乏回溯和全局优化
       3. 依赖问题的贪心选择性质
       4. 可能得到近似解
       5. 需要证明贪心选择性质

• 不能保证全局最优解

贪心算法每一步只考虑当前的局部最优解，并不考虑这个选择对未来步骤的影响。因此，贪心算法不能保证一定能得到全局最优解。在某些情况下，贪心选择可能会导致陷入局部最优解而无法跳出，从而得到的解决方案不是全局最优的。

• 缺乏回溯和全局优化

贪心算法的设计思想是一次选择一步最优解，然后不再进行回溯和重新优化。这使得贪心算法不能考虑前面的选择是否会对后续决策产生不利影响。缺乏回溯和全局优化可能导致错过一些潜在的全局最优解。

• 依赖问题的贪心选择性质

贪心算法适用于那些具有贪心选择性质和最优子结构的问题。如果问题的特性不满足这些条件，贪心算法可能不适用或得到不够优化的解。有些问题可能需要更复杂的算法设计才能得到更精确的解决方案。

• 可能得到近似解

尽管贪心算法在某些情况下可以得到近似的全局最优解，但这并不是保证。对于一些问题，贪心算法的近似解可能与真实的全局最优解相差较大，影响问题求解的准确性和可靠性。

• 需要证明贪心选择性质

在使用贪心算法解决问题时，需要证明问题具有贪心选择性质和最优子结构。这要求对问题的性质进行深入研究和分析，增加了算法设计的复杂性和困难程度。

3.应用范围

文章目录：

       1. 最优化问题
       2. 资源分配问题
       3. 组合优化问题
       4. 负载均衡问题
       5. 网络路由问题

• 最优化问题

贪心算法适用于许多最优化问题，特别是那些具有贪心选择性质和最优子结构的问题。通过每次选择当前的最优解，贪心算法能够逐步构建全局最优解或近似最优解。最优化问题的典型应用包括最小生成树（MST）、最短路径、霍夫曼编码等。

• 资源分配问题

贪心算法在资源分配问题中也有广泛应用。这些问题通常涉及将有限的资源分配给不同的任务或项目，以最大化或最小化某种指标。贪心算法通过选择当前局部最优的资源分配策略，可以在一定程度上得到全局最优的资源分配方案。

• 组合优化问题

组合优化问题是指在给定的集合中寻找满足特定条件的组合。贪心算法在组合优化问题中常常可以用于快速近似解。例如，背包问题、旅行商问题（TSP）等都是组合优化问题，贪心算法可以提供高效的解决方案。

• 负载均衡问题

负载均衡问题是在分布式系统中，如何合理地分配任务或工作量，使得各个节点的负载尽量均衡。贪心算法可以通过选择最优的任务分配方式来达到负载均衡的目标。

• 网络路由问题

在网络通信中，路由问题涉及如何选择最优路径来传输数据。贪心算法可以用于选择最短路径，以提高网络通信的效率。

值得注意的是，虽然贪心算法在上述问题中表现出色，但它并不适用于所有问题。贪心算法的应用范围受到问题本身特性的限制。在使用贪心算法时，必须确保问题具有贪心选择性质和最优子结构，以保证贪心选择的局部最优解能够构成全局最优解或近似最优解。如果问题的特性不满足这些条件，贪心算法可能无法得到正确的解决方案。

6. 例题讲解

文章目录：

       1. P1223 排队接水
       2. P1094 [NOIP2007 普及组] 纪念品分组
       3. P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

1. P1223 排队接水

题目传送门

事实上，我看不出来这和贪心有什么关系

要让平均排队时间最小，就要让打水快的人往前排

证：

设有 n 个人打水，每个人的打水时间分别为 x _ {1},x _ {2},x _ {3},...,x _ {n}

则打水时间总和为x _ {1} \times (n - 1) + x _ {2} \times (n - 2) + ... + x _ {n-1} \times 1 + x _ {n} \times 0

要让打水总时间最小，就要让x _ {1} < x _ {2} < ...< x _ {n}

所以我们可得

1.排序，对输入进行排序，使其变成x _ {1} < x _ {2} < ...< x _ {n}这个序列

2.累加时间，如果用x _ {1} \times (n - 1) + x _ {2} \times (n - 2) + ... + x _ {n-1} \times 1 + x _ {n} \times 0会比较麻烦， 我们换一个方式,令 x _ {0} = 0 我们求x _ {0} + (x _ {0} + x _ {1}) + ... + (x _ {0} + x _ {1} + ... + x_{n-1})

3.把加完的时间除以 n，再把x _ {1},x _ {2},...,x _ {n}和时间输出

题目传送门

首先看到各位大佬用的都是堆或桶我也就放心了 当然我做这道题的思路也是堆

但是,简单的介绍堆并不是我写这道题的目的

我写这篇题解，是为了让各位了解一下大家平时很少注意的 C++ 的某个方面 发掘更多新玩法

把你们从算法的深渊拉出来

—————————————分割线———————————————

————————————正文开始———————————————

————————————此篇为 C++ 福利——————————

第一部分

设想一下，某一天，当你兴致勃勃的在洛谷里刷题时，看到了一道叫“合并果子”的题，你不屑地扫了一遍题目，心想着这种模板题也好意思入选提高组。迅速用小根堆将它 AC 后，却对堆产生了浓厚兴趣，便又找来一道与堆有关的题，惊讶发现该题的数据 long long 装不下，于是又写了一篇高精，但是在结合两者时却死活都结合不了，最后关掉电脑，生无可恋。

换一个场景，很多人都用过，至少接触过 C++的 STL 库，那么应该就很熟悉形似这样的东西

priority_queue < int, vector<int>, greater<int> >;
vector < long long >;
queue <double >;

一些细心的人可能就会发现，在 <> 简直可以装下任何数据类型，那么C++，到底是如何实现这种操作的呢？

—————————分割线——————————

—————————分割线——————————

—————————分割线——————————

第二部分 我们回到第一个设想，你在写了一篇堆模板后，为了让它能够支持不同数据类型，对代码进行了这样的改动

typedef item int;
class heap{
    private:
        item h[1001];
        int len;
    public:
        heap();
        void push(item const &);
        void pop();
}

这样就可以针对不同数据类型，运用不同的堆

typedef item long long;
class heap{
    private:
        item h[1001];
        int len;
    public:
        heap();
        void push(item const &);
        void pop();
}

typedef item string;
class heap{
    private:
        item h[1001];
        int len;
    public:
        heap();
        void push(item const &);
        void pop();
}

但这样却有两个致命的缺陷，那就是每次使用，都得改一下头文件，并且不能同时存在两个不同类型的堆。那么应该怎样做呢？你不禁陷入了沉思。

第三部分

聪明的你当然知道如何使用网络来使自己的生活更加便利，于是你在“百度一下”中打出了

priority_queue < int, vector<int>, greater<int> >

并按下了回车，结果跳出来满屏的“容器”啊，“CSDN博客”啊之类的，让你心烦意燥，分分钟原地爆炸。或是瞅着顺眼的点了一篇，耐着性子看完，最后学到了 NOTHING。

但是，一个词语突然从你眼前闪过，这个词语仿佛有着魔力，使你的视线一下子聚焦在了它身上，你的脑中仿佛浮现出了什么，又仿佛没有。

“类模板”

你轻轻地念叨着这词。

第四部分

类模板，模板的类型参数由关键字 class 或关键字 typename 及其后的标识符构成。在模板参数表中关键字 class 和 typename 的意义相同。(在标准 C++之前关键字 typename 没有被支持 ，把这个关键字加入到 C++中的原因是因为有时必须要靠它来指导编译器解释模板定义。)，是对一批仅仅成员数据类型不同的类的抽象，程序员只要为这一批类所组成的整个类家族创建一个类模板，给出一套程序代码，就可以用来生成多种具体的类，(这类可以看作是类模板的实例)，从而大大提高编程的效率。———— 360百科

我们举个列子：

template<typename item>
class smallest_heap{
    private:
        item heap[10001];
        int len;
    public:
        smallest_heap();
        void push(item const &);
        void pop();
        item top();
        int size();
        bool empty();

};

其中第一排的

template<typename item>

就是关键，它指出接下来声明的某个类是模板，也就是部分数据类型不确定，暂且将这种数据类型叫做

item

而方法（也就是成员函数），相信各位大佬都会写。但是，要注意，在操作时，有一些不同指出

template<typename item>
smallest_heap<item>::smallest_heap(){
    len=0;
    memset(heap,0,sizeof(heap));
}

template<typename item>
void smallest_heap<item>::push(item const &n){
    heap[++len]=n;
    int son=len,father=son/2;
    while(heap[son]<heap[father] && father>=1){
        swap(heap[son],heap[father]);
        son=father,father=son/2;
    }
}

template<typename item>
void smallest_heap<item>::pop(){
    swap(heap[1],heap[len]);
    heap[len--]=0;
    int father=1,son=2;
    while(son<=len){
        if(son<len && heap[son]>heap[son+1]) son++;
        if(heap[father]>heap[son]){
            swap(heap[father],heap[son]);
            father=son,son=father*2;
        }else break;
    }
}

template<typename item>
item smallest_heap<item>::top(){
    return heap[1];
}

template<typename item>
int smallest_heap<item>::size(){
    return len;
}

template<typename item>
bool smallest_heap<item>::empty(){
    return len;
}

在每个方法前，都加了一排

template<typename item>

这是因为类的数据类型不确定，自然方法数据类型也不确定，所以用

item

来替代。并且在声明方法所属域时，也不是

smallest_heap::smallest_heap()

而是

smallest_heap<item>::smallest_heap()

最后送上 AC 代码以及小根堆，大根堆模板一份

番外