[已解决]贪心算法详细讲解

学习编程中的Ben

如题,最近最测试题是遇到了贪心算法,结果不会!!!
我网上搜了搜,很多示例讲解我都看不太懂,比如以下这题:

题目描述:

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
假设某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入n个导弹依次飞来的高度（给出的高度数据是不大于30000的正整数），计算如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
比如：有8颗导弹，飞来的高度分别为
389 207 175 300 299 170 158 165
那么需要2个系统来拦截，他们能够拦截的导弹最优解分别是： 系统1：拦截 389 207 175 170 158
系统2：拦截 300 299 165

明明一个系统也可以完成拦截啊?拦截顺序:389 300 299 207 175 170 165 158
我不太会阅读理解,有可能会理解错误哈


所以
有没有人可以给我清楚地讲解一下贪心算法,并且拿一个示例题目,经典一点的,并给出c++实现代码?,我想要人工哈,你是ChatGPT就别回答问题了
或者你们给我一个讲解的清楚的文章也行



@Ewan-Ahiouy @zhangjinxuan @不二如是 @liuhongrun2022 @歌者文明清理员

最佳答案

月排行榜 / 总排行榜

Ewan-Ahiouy

2023-7-27 20:11:45

http://w466763.s144.myverydz.cn/ ... p;tid=19&extra= 元豪写的

跳转到最佳答案楼层

Ewan-Ahiouy

http://w466763.s144.myverydz.cn/ ... p;tid=19&extra= 元豪写的

isdkz

贪心算法是一种常见的解决问题的策略，它在每一步都选择当前状态下的最优解，希望最终能够得到全局最优解。对于这个导弹拦截系统问题，我们可以使用贪心算法来解决。

首先，我们来理解一下这个问题。导弹拦截系统的特点是后续的炮弹不能高于前面的炮弹，而我们的目标是用尽可能少的系统来拦截所有导弹。我们需要找到一种拦截导弹的策略，使得每个导弹都能被拦截，并且尽可能少地使用系统。

为了达到最少的系统数，我们可以采用贪心策略：从左到右遍历导弹的高度，维护一个记录当前系统拦截高度的序列。对于每颗导弹，我们按以下规则处理：

1. 如果当前导弹的高度严格小于等于已有系统中最高的导弹高度，则将该导弹拦截并放入相应系统中，因为它不会比已有系统中的任何一颗导弹更高。
2. 如果当前导弹的高度严格大于已有系统中最高的导弹高度，则需要新建一个系统来拦截该导弹，因为它不能与已有系统中的任何导弹一起拦截。

通过这种贪心策略，我们可以保证每颗导弹都能被拦截，而且用尽可能少的系统。接下来，我会给出一个示例的C++实现代码来解决这个问题。

#include <iostream>
#include <vector>

using namespace std;

int missileInterception(vector<int>& missiles) {
    vector<int> systems; // 记录每个系统的最高导弹高度

    for (int height : missiles) {
        int systemIndex = -1;
        // 在已有系统中找到第一个能拦截当前导弹的系统
        for (int i = 0; i < systems.size(); i++) {
            if (height <= systems[ i]) {
                systemIndex = i;
                break;
            }
        }

        // 如果找不到合适的系统，新建一个系统来拦截当前导弹
        if (systemIndex == -1) {
            systems.push_back(height);
        } else {
            // 找到合适的系统，将当前导弹拦截并更新该系统的高度记录
            systems[systemIndex] = height;
        }
    }

    return systems.size();
}

int main() {
    vector<int> missiles = {389, 207, 175, 300, 299, 170, 158, 165};
    int systemsNeeded = missileInterception(missiles);
    cout << "最少需要 " << systemsNeeded << " 套导弹拦截系统来拦截所有导弹。" << endl;

    return 0;
}

在这个示例代码中，我们使用了一个 systems 向量来记录每个系统的最高导弹高度。然后，我们遍历导弹高度并按照贪心策略处理每颗导弹。最后返回 systems 向量的大小即为最少需要的系统数。

希望这个示例能够帮助你理解贪心算法以及如何用它来解决导弹拦截系统问题。如果有其他问题，请随时问我。

Mike_python小

在计算机科学中，贪心算法是一种通过每一步的局部最优选择来达到全局最优解的算法策略。贪心算法通常适用于求解最优化问题，且问题具备贪心选择性质，即通过选择当前最优解来进行求解，并不会回溯或者考虑未来可能的情况。

假设有一个需要安排的活动列表，每个活动都有一个开始时间和结束时间。只有一个资源可以被用于一次活动，而且每个活动都需要独占使用这个资源。要求设计一个算法，从活动列表中选出最大数量的互不相容的活动。

例如，给定活动列表如下：

活动编号 | 开始时间 | 结束时间
--------|---------|--------
A1      | 1       | 4
A2      | 3       | 5
A3      | 0       | 6
A4      | 5       | 7
A5      | 3       | 9
A6      | 5       | 9
A7      | 6       | 10
A8      | 8       | 11
A9      | 8       | 12
A10     | 2       | 14

要求选择出的互不相容的活动数量最大。


1. 将活动列表按照结束时间进行升序排序，选择最早结束的活动作为第一个活动。
2. 从剩余的活动中，选择开始时间晚于上一个选中活动结束时间的活动，将其加入到选择集合中，并更新上一个选中活动。
3. 重复步骤2，直到所有活动遍历完毕。

#include <iostream>
#include <vector>
#include <algorithm>

// 活动结构体
struct Activity {
    int start;
    int end;
};

// 比较函数，按照结束时间升序排序
bool compare(Activity a, Activity b) {
    return a.end < b.end;
}

// 寻找最大数量的互不相容活动
int findMaxActivities(std::vector<Activity>& activities) {
    // 对活动进行排序
    std::sort(activities.begin(), activities.end(), compare);
    
    int count = 1;  // 至少有一个活动可以选择
    int prevEnd = activities[0].end;  // 第一个活动的结束时间
    
    // 从剩余活动中选择
    for (int i = 1; i < activities.size(); i++) {
        if (activities[i].start >= prevEnd) {
            count++;
            prevEnd = activities[i].end;
        }
    }
    
    return count;
}

int main() {
    std::vector<Activity> activities = {
        {1, 4},
        {3, 5},
        {0, 6},
        {5, 7},
        {3, 9},
        {5, 9},
        {6, 10},
        {8, 11},
        {8, 12},
        {2, 14}
    };
    
    int maxActivities = findMaxActivities(activities);
    std::cout << "最大互不相容活动数量: " << maxActivities << std::endl;
    
    return 0;
}

陶远航

贪心算法是一种常用的优化算法，适用于一些可以通过贪心选择策略得到全局最优解的问题。它的核心思想是在每一步选择中都采取当前状态下的最优决策，以期望最终的结果也是最优的。

对于你提到的导弹拦截系统问题，我们可以使用贪心算法来解决。首先，让我们详细解释一下贪心算法的思路和步骤。

1. 理解问题：首先，我们需要充分理解问题的要求和约束条件。在这个问题中，我们需要拦截所有的导弹，并且每个拦截系统的炮弹高度不能高于前一个。

2. 分析最优子结构：贪心算法的关键是找到最优子结构，即每一步都选择局部最优解，以期望最终得到全局最优解。在这个问题中，我们可以考虑每一次选择最大的高度导弹进行拦截，因为这样可以尽量减少需要的拦截系统数量。

3. 设计贪心策略：根据最优子结构，我们可以设计贪心策略。对于每个导弹，我们检查它是否满足拦截系统的要求：即它的高度不能高于之前拦截的导弹。如果不能满足，则需要增加一个新的拦截系统。通过这种贪心策略，我们可以保证每一步都是局部最优的选择。

4. 实现算法：根据上述策略，我们可以使用以下步骤实现贪心算法来解决导弹拦截系统问题：

   · 将导弹高度存储在一个数组中。
   · 初始化拦截系统数量为 1。
   · 从第二个导弹开始遍历数组，比较当前导弹高度与之前拦截的导弹高度。
   · 如果当前导弹高度大于之前拦截的导弹高度，则需要增加一个新的拦截系统，并更新之前拦截的导弹高度为当前导弹高度。
   · 如果当前导弹高度小于或等于之前拦截的导弹高度，则可以继续使用之前的拦截系统。

下面是对应的 C++ 代码实现：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> heights = {389, 207, 175, 300, 299, 170, 158, 165};
    int n = heights.size();

    int interceptors = 1;
    int currentHeight = heights[0];

    for (int i = 1; i < n; i++) {
        if (heights[ i] > currentHeight) {
            interceptors++;
            currentHeight = heights[ i];
        }
    }

    std::cout << "最少需要配备的导弹拦截系统数量为：" << interceptors << std::endl;

    return 0;
}

在这个示例中，我们使用一个 heights 数组存储导弹的高度。然后，我们遍历数组，并根据贪心策略更新拦截系统数量和当前拦截的导弹高度。最后输出所需的拦截系统数量。

希望这个解释和示例代码能够帮助你理解和学习贪心算法。如果你还有其他问题，请随时提问！
如果问题已经解决，请设置最佳答案

歌者文明清理员

算法或者非python不要找我

学习编程中的Ben

isdkz 发表于 2023-7-27 20:12
贪心算法是一种常见的解决问题的策略，它在每一步都选择当前状态下的最优解，希望最终能够得到全局最优解。 ...

一.我要人工
二.我主要是想了解贪心算法,

liuhongrun2022

不会

学习编程中的Ben

liuhongrun2022 发表于 2023-7-27 20:15
不会

QAQ

Ewan-Ahiouy

上qq

zhangjinxuan

贪心不证明，爆零两行泪。

zhangjinxuan

比方说，你要从 n 个数字里面选择 m 个数字，要让数字之和最大。

贪心流程：从大到小选择数字。
证明：若不从大到小选择，则目前选择的数字一定小于剩余未选择数字的其中一个或一些，那么累加起来的和就一定不是最优的一个解。

zhangjinxuan

我没看帖子内容，看了一下，这道题应该要用 LIS 来做，LIS 是一道 DP 的题目，但时间复杂度 O(N^2)，因此需要贪心来优化。

具体怎么贪心，我看你贪心是处于入门的水平，目前学习 LIS 可能会有点困难，但是如果你还是要学的话我可以给你一些参考。

zhangjinxuan

Ewan-Ahiouy 发表于 2023-7-27 20:29
http://w466763.s144.myverydz.cn/forum.php?mod=viewthread&tid=19&extra= 元豪写的

原来你也知道梦想论坛

Ewan-Ahiouy

zhangjinxuan 发表于 2023-7-27 20:32
原来你也知道梦想论坛

嗯

sfqxx

zhangjinxuan 发表于 2023-7-27 20:32
原来你也知道梦想论坛

O(nlogn)能做到吗

tommyyu

zhangjinxuan 发表于 2023-7-27 20:26
贪心不证明，爆零两行泪。

01背包用贪心是个好主意我们只需要每次挑一个价值最大的就可以了这题也是一样，直接拦截最高的，然后拦截第二高的完全不需要任何证明
爆零别怪我

zhangjinxuan

tommyyu 发表于 2023-7-27 21:00
01背包用贪心是个好主意我们只需要每次挑一个价值最大的就可以了这题也是一样，直 ...

《别怪我》

Ewan-Ahiouy

题目描述:
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
假设某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入n个导弹依次飞来的高度（给出的高度数据是不大于30000的正整数），计算如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
比如：有8颗导弹，飞来的高度分别为
389 207 175 300 299 170 158 165
那么需要2个系统来拦截，他们能够拦截的导弹最优解分别是： 系统1：拦截 389 207 175 170 158
系统2：拦截 300 299 165

明明一个系统也可以完成拦截啊?拦截顺序:389 300 299 207 175 170 165 158
我不太会阅读理解,有可能会理解错误哈

？？？？
他发射导弹是有顺序的啊

Ewan-Ahiouy

这是哪一题，我去做做看