C++算法之贪心算法

这篇具有很好参考价值的文章主要介绍了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<bits/stdc++.h>
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 < len && s[i] == '0'; ++i);//去除前导0 
    for(; i < len; ++i)
    {
        while(an > 0 && a[an] > s[i] && ct < k)//a[an]为前一个数 s[i]为后一个数,当a[an]>s[i]时,删除a[an]
        {
            an--;
            ct++;//删除数字个数加1
        }
        a[++an] = s[i];//无论如何s[i]都会填充进数组a
    }
    while(ct < k)//删除末尾的k-ct个元素
    {
        an--;
        ct++;
    }
    for(i = 1; i <= an && a[i] == '0'; ++i);//去除前导0 
    if(i > an)//如果前导0去完,就没有可以输出的了,说明原来的结果是0 
        cout << "0";
    else
        while(i <= an)
            cout << a[i++];
    return 0;
}

 3.2 接水问题

接水问题

【题目描述】

学校里有一个水房,水房里一共装有m个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为1。

现在有n名同学准备接水,他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号,i号同学的接水量为wi。接水开始时,1到m号同学各占一个水龙头,并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj后,下一名排队等候接水的同学k马上接替j同学的位置开始接水。这个换人的过程是瞬间完成的,且没有任何水的浪费。即j同学第x秒结束时完成接水,则k同学第x+1 秒立刻开始接水。 若当前接水人数n’不足m,则只有n’个龙头供水,其它m-n’个龙头关闭。

现在给出n名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒。

【输入】

第1行2个整数n和m,用一个空格隔开,分别表示接水人数和龙头个数。

第2 行n个整数 w1、w2、……、wn,每两个整数之间用一个空格隔开,wi表示 i 号同学的接水量。

【输出】

输出只有一行,1个整数,表示接水所需的总时间。

【输入样例】

5 3
4 4 1 2 1

【输出样例】

4

【样例输入#2】

8 4

23 71 87 32 70 93 80 76

【样例输出#2】

163

【提示】

输入输出样例1解释:

第1秒,3人接水。第1秒结束时,1、2、3号同学每人的已接水量为1,3号同学接完水,4号同学接替3号同学开始接水。

第2秒,3人接水。第2秒结束时,1、2号同学每人的已接水量为2,4号同学的已接水量为1。

第3秒,3人接水。第3秒结束时,1、2号同学每人的已接水量为3,4号同学的已接水量为2。4号同学接完水,5号同学接替4号同学开始接水。

第4秒,3人接水。第4秒结束时,1、2号同学每人的已接水量为4,5号同学的已接水量为1。1、2、5号同学接完水,即所有人完成接水。

总接水时间为4秒。

#include <bits/stdc++.h>
using namespace std;
struct Pair
{
    int n, t;//n:水龙头编号 t:结束时间
    Pair(){}
    Pair(int a, int b):n(a),t(b){}
    bool operator < (const Pair &b) const
    {
        return b.t < t;//结束时间早更优先 
    } 
};
int main()
{
    priority_queue<Pair> pq;
    int n, m, w[10005], mni, mx = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        cin >> w[i];
    for(int i = 1; i <= m; ++i)
        pq.push(Pair(i, w[i]));
    for(int i = m+1; i <= n; ++i)//已知m<=n 
    {
        int mni = pq.top().n, t = pq.top().t;
        pq.pop();
        pq.push(Pair(mni, t + w[i]));//第mni水龙头接水结束时间增加w[i]
    }
    while(pq.empty() == false)
    {
        mx = max(mx, pq.top().t);
        pq.pop();
    }
    cout << mx;
    return 0;
}

创作不易,白嫖不好,各位的支持和认可,就是我创作的最大动力,如果喜欢我的文章,给个关注吧!

冰焰狼 | 文

如果本篇博客有任何错误,请批评指教,不胜感激 !文章来源地址https://www.toymoban.com/news/detail-811465.html

到了这里,关于C++算法之贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 重拾C++之菜鸟刷算法第15篇 --- 贪心算法

    题目 给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。 在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。 返回 你能获得的 最大 利润 。 122. 买卖股票的最佳时机 II - 力扣(

    2024年03月20日
    浏览(40)
  • 秒懂百科,C++如此简单丨第二十天:贪心算法2

    目录 Everyday English 前言 洛谷 P1031 均分纸牌 题目描述 思路点拨 AC代码 洛谷 P1094 纪念品分组 题目描述 样例输入 样例输出  思路点拨 AC代码 洛谷 P2660 zzc 种田  题目描述 思路点拨 AC Code 结尾 Don\\\'t miss the opportunity. 机不可失,时不再来。 这节课是贪心算法的习题课,我们会讲解

    2024年02月20日
    浏览(39)
  • 2023华为OD机试真题【区间交叠/贪心算法】【Python Java C++】

    给定坐标轴上的一组线段,线段的起点和终点均为整数并且长度不小于1,请你从中找到最少数量的线段,这些线段可以覆盖住所有线段。 输入描述 第一行输入为所有线段的数量,不超过10000,后面每行表示一条线段,格式为”x,y”, x和y 分别表示起点和终点,取值范围是

    2024年02月13日
    浏览(56)
  • 算法分析与设计-会场安排问题(贪心)(通俗易懂,附源码和图解,含贪心选择性质和最优子结构性质的证明)(c++)

    (一)题目 问题描述 假设在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点有着不同颜色的最小着色数,相当于

    2024年02月07日
    浏览(95)
  • 【华为OD机考 统一考试机试C卷】贪心歌手(C++ Java JavaScript Python C语言)

    目前在考C卷,经过两个月的收集整理, C卷真题已基本整理完毕 抽到原题的概率为2/3到3/3, 也就是最少抽到两道原题。 请注意:大家刷完C卷真题,最好要把B卷的真题刷一下,因为C卷的部分真题来自B卷。 另外订阅专栏还可以联系笔者开通在线OJ进行刷题,提高刷题效率。

    2024年02月20日
    浏览(47)
  • [开发语言][C++]:递增递减运算符

    递增运算符和递减运算符为对象的+1和-1提供了简洁的书写形式。 自增自减运算符的应用: 这两个运算符除了应用在算术运算,还可应用于迭代器,因为很多迭代器并不支持算术运算。 递增和递减运算符有两种书写形式:前置版本和后置版本。 前置版本 ++i --i :首先将运算

    2024年01月25日
    浏览(52)
  • 第七十七篇:车辆安全-车载软件C++语言开发指南(AUTOSAR C++)

    C++是面向对象的编程,比C语言更加复杂,抽象程度高,但C++在一些图像处理、系统、控件的编程方面,实用性更强,具有自己的编程优势。在车载嵌入式系统的开发中,C和C++都具有重要的作用。C++语言所使用的面向对象的编程技术如封装、继承和多态性极大的提高了在大规

    2024年02月04日
    浏览(84)
  • [Daimayuan] 吃糖果(C++,贪心)

    桌子上从左到右放着 n n n 个糖果。糖果从左到右编号,第 i i i 块糖果的重量为 w i w_i w i ​ 。小明和小红要吃糖果。 小明从左边开始吃任意数量的糖果。(连续吃,不能跳过糖果) 小红从右边开始吃任意数量的糖果。(连续吃,不能跳过糖果) 当然,如果小明吃了某个糖果

    2024年02月02日
    浏览(44)
  • [开发语言][c++][python]:C++与Python中的赋值、浅拷贝与深拷贝

    写在前面 :Python和C++中的赋值与深浅拷贝,由于其各自语言特性的问题,在概念和实现上稍微有点差异,本文将这C++和Python中的拷贝与赋值放到一起,希望通过对比学习两语言实现上的异同点,加深对概念的理解。 C++中所谓的 浅拷贝 就是由(系统默认的) 拷贝构造函数对

    2024年02月02日
    浏览(57)
  • 《数据结构、算法与应用C++语言描述》-列车车厢重排问题

    完整可编译运行代码见:Github::Data-Structures-Algorithms-and-Applications/_10Train_carriages_rearrangement/ 一列货运列车有 n 节车厢,每节车厢要停靠在不同的车站。假设 n个车站从 1 到n 编号,而且货运列车按照从n到1的顺序经过车站。车厢的编号与它们要停靠的车站编号相同。为了便于从

    2024年04月10日
    浏览(67)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包