基于活动选择问题的贪心算法

Kubrnete 等级 494 1 0

目录

问题描述:

输入格式

输出格式

算法描述

算法分析

算法图示


问题描述:

Coda从0时刻开始观看直播,到 t 时刻结束。一共有n场直播可被选择,已知所有直播场次的起止时间和主播名称,其中第i场直播从ai时刻开始,bi时刻结束,主播名称为ci,每场直播的起始时间和结束时间都是整点(不保证所有直播全程都在Coda观看的时间段内)。Coda同时只能观看一场直播,并且必须看完正在观看的直播,才能选择下一场尚未开始的直播。

请求出Coda在这段时间内最多能观看几场直播,并按照观看顺序输出观看的每个主播的名称。

输入格式

第一行包含两个整数t,分别表示已知的直播场数和结束观看的时刻。

接下来n行,每行包含两个整数ab,以及一个由小写字母组成的字符串c,分别表示每场直播的起始时间,结束时间,主播名称。

输出格式

第一行包含一个整数,输出最多能观看多少场直播。

接下来n行,每行输出一个字符串,按照观看顺序输出所看主播的名称。

基于活动选择问题的贪心算法)基于活动选择问题的贪心算法

这是一个经典的活动选择问题:

给出n个活动的开始时间和结束时间,同一时间只能参与一个活动,要找出可以参与的最多活动的个数。

题目老贪心了。我们知道,贪心算法会在每一步中直接选择当前看来最好的选择。在求解过程中,选择一个活动方法最优解,然后对剩余的子问题(包含与已选择的活动兼容的活动)进行求解。

贪心算法通常都是这种自顶向下的设计:做出一个选择,然后求解剩下的那个子问题,而不是自底向上求解出很多子问题,然后再做出选择。

算法描述

(如果分析或证明看不懂可直接点击前往算法图示部分)

基于活动选择的贪心策略,能得出以下定理:

对于任意非空子问题Sij,设am是Sij中具有最早结束时间的活动,那么

(1)活动am在Sij中的某最大兼容活动子集中被使用。

(2)子问题Sim为空,所以选择am将使子问题Smj为唯一可能非空的子问题。

  1. 假定有一个n个活动的集合S={a1,a2,a3...,an},
  2. 这些活动使用同一个资源(例如同一个阶梯教室),而这个资源在某个时刻只能供一个活动使用。每个活动ai都有一个开始时间si和一个结束时间fi,设当前时间为now,占用资源结束时间为t
  3. 其中now<=si<fi<=t。如果被选中,任务ai发生在半开时间区[si,fi)期间。如果两个活动ai和aj满足[si,fi)和[sj,fj)不重叠,则称它们是兼容的。
  4. 若si>=fj,或sj>=fi,则ai和j是兼容的。在活动选择问题中,我们希望选出一个最大兼容活动集。

在最开始时选出结束时间最早的那个活动,就能够为其他活动尽可能地腾出更多时间。而后,每一步都在剩下的活动中选取,也遵循类似的原则。

因此,我们要选择活动中结束时间最早并且开始时间大于或等于先前所选活动的结束时间的下一个活动。

即:Step①:根据活动结束时间对活动递增排序;

  Step②:对排序后的活动,如果开始时间大于或等于上一个选中活动的结束时间(初始活动时间为0),则选中该活动

算法分析

对于给定的一组活动为S = {1,2,3,.. n},并且已按活动结束时间对所有活动进行排序。 贪心策略总是选择【活动1】。为什么【活动1】始终是最佳解决方案之一?下面给出简单的证明:

假设存在除了【活动1】以外的另一个最佳解决方案S,并且S选择的第一个活动是【活动k】,而不是【活动1】。现在我们来说明,把【活动k】替换成【活动1】,得到的新方案S‘,{B-{k}}U{1},必定仍然是一个最佳解决方案,说明如下:因为S 中的活动是独立的,而在排序队列中,【活动1】在所有活动中具有最小的结束时间,因为k不等于1,【活动k】的完成时间必定是大于等与【活动1】的完成时间,因此把【活动k】换成【活动1】后的新方案S‘必定也是最佳解决方案。

算法图示

看不懂没关系(我也).请参考我随手画的图,也许不严谨,但将尽可能直观。

Case1:活动2与活动3的结束时间相同

基于活动选择问题的贪心算法)基于活动选择问题的贪心算法

(不要小看图中的虚线,虚线表示的是每个活动的结束时间,虽然挺丑的,但每次做选择的时候都得通过这一条条虚线划分区域)

由于题目要求活动按时间顺序输出,因此活动2的起始时间在活动1的起始时间和结束时间之间的情况都是一样的,即与下图的情况等价

基于活动选择问题的贪心算法)基于活动选择问题的贪心算法

显然,先选择活动1为后面腾出多余的时间。此时活动1与活动3属于活动2的活动时间范围内的子集(即能够选择活动2,必能选择活动1+活动3)。

Case2:活动3结束时间晚于活动2结束时间

基于活动选择问题的贪心算法)基于活动选择问题的贪心算法

或许在这种情况下你无法确定该选出哪个活动,至少可以说:活动2看起来也不差?那么我们引入一个新的活动4

基于活动选择问题的贪心算法)基于活动选择问题的贪心算法

这里其实我们很容易地可以做出以下决定:

只要活动2的结束时间晚于活动1,选择活动1后总是能够选择活动3或活动4因此选择活动1是第一步的最优解。

②选出活动1以后可以将活动2给去掉。即

基于活动选择问题的贪心算法)基于活动选择问题的贪心算法

我们可以发现,选出活动1后,在剩下能够选择的活动中又回到了上一次做决定时面对的情况

这时只要继续选出结束时间更早的活动,就是题目的最优解。(如果结束时间相同,按照先来先进行即可)

以下图为例

基于活动选择问题的贪心算法)基于活动选择问题的贪心算法

首先,将每个活动按结束时间递增排序。我们将选出1,然后去掉2,选中4,然后去掉3......

附此题代码:

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, string> p;
typedef pair<int, p> Acti; //活动结构体
int main()
{
    int n, t, a, b, end = 0; //end是当前活动时间,初始值为0,起始时间大于或等于当前时间的活动均为可选活动
    cin >> n >> t;
    Acti activities[n];
    string ans[n];
    for (int i = 0; i < n; i++)
        cin >> activities[i].second.first >> activities[i].first >> activities[i].second.second;
    sort(activities, activities + n);//step1:对活动的结束时间排序(因为需要按起始时间顺序输出,就直接把整个结构体排了吧)
    int count = 0;
    for (int i = 0; i < n; i++)                
        if (activities[i].second.first >= end) //step2:对排序后的活动,如果开始时间大于或等于上一个选中活动的结束时间,则选出该活动.
        {
            if (activities[i].first > t) //当活动中的结束时间大于活动结束的时刻就停止
                break;
            ans[count++] = activities[i].second.second;
            end = activities[i].first; //当前活动时间更新
        }
    cout << count << endl;
    for (int i = 0; i < count; i++)
        cout << ans[i] << endl;
}

本文转自 https://blog.csdn.net/guanguandaren/article/details/107911535,如有侵权,请联系删除。

收藏
评论区

相关推荐

C++概述
概述 C 是静态,可编译,通用,大小写敏感,格式自由的编程语言,它支持程序化,面向对象的,和泛型编程方式。 C 被看作是中间层语言,因为它同时包含了低级语言和高级语言的特性。 C 是于 1979 年在新泽西的茉莉山丘的贝尔实验室由 Bjarne Stroustrup 开发的,它是 C 语言的加强版,最开始它被称作 “C with Classes”,但是
C++ 基本语法
C 程序可以定义为对象的集合,这些对象通过调用彼此的方法进行交互。现在让我们简要地看一下什么是类、对象,方法、即时变量。 对象 对象具有状态和行为。例如:一只狗的状态 颜色、名称、品种,行为 摇动、叫唤、吃。对象是类的实例。 类 类可以定义为描述对象行为/状态的模板/蓝图。 方法 从基本上说,一个方法表示一种行为。一个类可以包含多个
统计字符串中字符出现的次数(Python版)
字符串转list python s 'aabbccd' list1 list(s) 方法一: python list1 'a', 'a', 'b', 'c', 'c', 'c', 'c' dict_cnt {} for value in list1: dict_cntvalue dict_cnt.get(value,
c++11 实现单例模式
C11出来后,里面新增加了好多好用的功能 下面的单例就是使用了C11中的标准库中的mutex和unique_prt 进行内存管理的. 此单例模式不用担心内存的释放问题 pragma once include <memory include <mutex template <class T class Singleton { public: ty
C语言_练习题(一)
前言: 看懂理解代码很容易,难的是把所理解的融会贯通,融合到实例中,你会发现事实和理论会有些许差别,编写实例能更好的帮你积累经验。 0x1 编写一个程序,要求提示输入一个ASCII码值(如,66),然后打印输入的字符。 代码: include <stdio.h int main(){ char i; printf("请输入一个ASCI
我的C语言基础
C语言32个关键字auto 声明自动变量short 声明短整型变量或函数int 声明整型变量或函数long 声明长整型变量或函数float 声明浮点型变量或函数double 声明双精度变量或函数char 声明字符型变量或函数struct 声明结构体变量或函数union 声明共用数据类型enum 声明枚举类型typedef 用以给数据类型取别名co
C语言基础习题50例(一)1-5
虎为百兽尊,罔敢触其怒。惟有父子情,一步一回顾。 习题1 有 1 、 2 、 3 、 4 个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?实现思路:显然,这个题目需要用到循环,并且是循环嵌套,先列出所有可能的组合,再去掉重复的组合即可。代码如下:cinclude <stdio.hint main(){ int i, j, k,
C语言基础习题50例(二)6-10
给大家推荐一门大数据Spark入门课程,希望大家喜欢。 习题6 用 号输出字母C的图案。实现思路:单行打印即可。代码如下:cinclude <stdio.h int main (void){ printf("\n"); printf("\n"); printf("\n"); printf("
C语言基础习题50例(三)11-15
你们看出神马了吗(\\^_\^\) 习题11 有一对兔子,从出生后第 3 个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少实现思路:从第1个月起,兔子对数分别为1、1、2、3、5、8、13、21...,显然是斐波拉契数列。代码如下:cinclude<stdio.hint mai
C语言基础习题50例(四)16-20
给大家介绍一堂Python入门课,感觉还不错,适合初学者入门。 习题16 输入两个正整数 m 和 n ,求其最大公约数和最小公倍数。实现思路:求两个数的最大公约数分别采用辗转相除法、辗转相减法、枚举法得到,最小公倍数用两个数之积除以最大公约数即可获得。方式一——辗转相除法:思路:(1)将两整数求余 a%b x;(2)如果x 0;则b为最大公
C语言基础习题50例(七)31-35
喜提头条号黄V,有兴趣的朋友可以关注一波,主写IT领域。 习题31 请输入星期几的第一个字母来判断一下是星期几,如果第一个字母一样,则继续判断第二个字母。实现思路:使用switch语句,如果第1个字母一样,则判断用情况语句或if语句判断第2个字母。也可以使用条件判断语句,实现相近。代码如下:cinclude<stdio.hint ma
C语言基础习题50例(十)46-50
知足常足,终身不辱。月圆缺,水满溢,事情到了极致一定会遭受祸患,只有懂得知足,才是富足。 习题46 宏define命令练习。实现思路:宏通过define命令定义,分为无参宏和带参宏,可以分别进行测试。这只是一种简单的字符串代换。代码如下:cinclude <stdio.hdefine TRUE 1define FALSE 0
游戏安全实践的一些思考
移动的游戏能够稳定健康的上线。主要需要依赖以下在四个方面:1.前端展示,或者说客户端正常运行。性能稳定不崩溃,不过热能够稳定运行。2.后端,或者游戏后台服务端的。不但要稳定。还有能在有限的服务器资源下,能承受大量的同时在线用户。而且要让游戏中的每个模块都能够承受承受大量的同时在线用户。3.安全也是重点之中。这既包括客户端,又包括服务端。客户端的安全,包括要防
小学生都能听懂的C++:第一讲 初识C++
视频链接:<https://www.bilibili.com/video/BV1hw411f7nz/请留下你的三连支持!!
JAVA回调机制(CallBack)之小红是怎样买到房子的??
JAVA回调机制CallBack 序言最近学习java,接触到了回调机制(CallBack)。初识时感觉比较混乱,而且在网上搜索到的相关的讲解,要么一言带过,要么说的比较单纯的像是给CallBack做了一个定义。当然了,我在理解了回调之后,再去看网上的各种讲解,确实没什么问题。但是,对于初学的我来说,缺了一个循序渐进的过程。此处,将我对回调机制的个人理解,按