首页 > 编程语言 >贪心算法-活动安排问题

贪心算法-活动安排问题

时间:2024-08-05 18:52:44浏览次数:12  
标签:int 安排 算法 printf 最优 活动 贪心

贪心算法

贪心算法总是选择当前看起来最优的选择(局部最优解),希望得到的结果是一个整体最优解。

但是,并非总是选择局部最优解就能够得到整体最优解,这一点需要在问题具有贪心选择性优化子结构时才成立。

贪心选择性

  • 贪心选择性:第一次做出贪心选择是正确的。

优化子结构

  • 问题具有优化子结构性质:第一次做完贪心选择后,得到一个与原问题定义相同(但输入不同的)的子问题。

贪心算法的基本要素

贪心选择性质

  1. 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。

  2. 贪心算法通常以自顶向下的方式进行,一迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。动态规划通常以自底向上的方式解决子问题。

最优子结构性质

  • 当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

4. 基本思路:

  • 建立数学模型来描述问题。
  • 把求解的问题分成若干个子问题。
  • 对每一子问题求解,得到子问题的局部最优解。
  • 把子问题的解局部最优解合成原来解问题的一个解。

活动安排问题定义

定义(活动)

设有n个活动的集合 E={1,2,…,n},其中每个活动都要求使用同一资源,而在同一时间内只有一个活动能使用这个资源。

定义(相容活动)

  • 若区间 [start_i, finish_i) 与区间 [start_j, finish_j) 不相交,则称活动i与活动j是相容的。也就是说,当 start_i >= finish_jstart_j >= finish_i 时,活动i与活动j相容。
    在这里插入图片描述
    在这里插入图片描述

活动安排问题的贪心算法思路

  1. 将各个活动按照活动结束时间 finish_i 排序,且 finish_1 <= finish_2 <= finish_3 …
  2. 选择活动1,要求该活动的结束时间最早。
  3. 从2开始按顺序比较各个活动,选择第一个与活动1相容的活动i。
  4. 从i+1开始按顺序考察各个活动,选择第一个与活动i相容的活动j。

每次选择与现有活动相容的结束时间最早的活动

举例详解算法过程

现在给出下列活动,其中 s 表示开始时间,f 表示结束时间。
在这里插入图片描述

1.根据算法,我们首选选择结束时间最早的活动作为第一个活动,第一个活动为:1
2.然后选择开始时间大于第一个活动的结束时间的活动,而且该活动的结束时间要求最早。显然是活动4;
3.同理,寻找开始时间晚于活动4的结束时间且结束时间最早的活动,一直到到无活动可选为止。
在这里插入图片描述

代码示例

#include<stdio.h>
#include<stdlib.h>
#define N 100
typedef struct {
int begin;
int end;
int flag;//标记是否被安排
}active;

int main()
{
    int num;//活动数量;
    active act[N];
    printf("请输入活动数量");
    scanf("%d",&num);
    printf("请输入活动的开始时间");
    for(int i=0;i<num;i++)
    {
        scanf("%d",&act[i].begin);
    }
    printf("请输入活动的结束时间");
    for(int j=0;j<num;j++)
    {
        scanf("%d",&act[j].end);
    }
    sort(act,num);
    greedy(act,num);
}

void greedy(active a[],int num)
{
     int current=0;//当前活动下标
     for(int i=0;i<num;i++)
     {
       a[i].flag = 0;//初始所有活动都未被安排
     }
     a[0].flag = 1;//排序后的第一个活动被安排
     /**
     //后面的活动开始的时间晚于当前活动开始的时间则相容
     //而当前活动初始下标为0,故后面的活动i下标要从1开始
     **/
     for(int i=1;i<num;i++)
     {
        if(a[i].begin >= a[current].end)
        {
           a[i].flag = 1;//相容,做标记
           current=i;//当前活动变为i
        }
     }

    //输出
    printf("\n\n");
    printf("按结束时间排序后的活动序号中,以下活动将被安排:\n\n");
    int count=0;
    for(int i=0;i<num;i++)
    {
        if(a[i].flag==1){
            count++;//被安排的活动数量;
            printf("活动%d :开始时间   结束时间:%d,%d\n",i,a[i].begin,a[i].end);
            printf("\n");
        }
    }
    printf("总计%d个活动被安排\n",count);
}

//按照结束时间非降序排序
void sort(active a[],int n)
{
    for (int i=0;i<n;i++)
    {
        for(int j=0;j<n-i-1;j++)
        {
            if(a[j].end>a[j+1].end){
                active temp;
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}


在这里插入图片描述

复杂度分析

()

标签:int,安排,算法,printf,最优,活动,贪心
From: https://blog.csdn.net/qq_52291558/article/details/140914671

相关文章

  • 「Day 2—贪心问题&分治&前缀和」
    贪心问题定义顾名思义,越贪越好。。。习题P1094[NOIP2007普及组]纪念品分组思路简单来说:最少的+最多的,利用双指针。代码#include<algorithm>#include<iostream>usingnamespacestd;intw,n;intp[30005];intmain(){cin>>w;cin>>n;for(inti=1;i......
  • 第九届世界3D渲染大赛:赛程安排、赛事规则
    ​第九届世界3D渲染大赛即将拉开帷幕,汇聚全球顶尖CG艺术家,展现最具有视觉盛宴的CG创作。那么该赛事的行程如何安排呢,赛事规则又是什么呢?本篇整理了赛事安排、赛事规则等内容,希望帮助大家。赛事主题:KineticRush(翻译:动能冲刺)赛事日期:2024年8月3日(美国时间)作品提交:2024年9月2日......
  • leetcode200. 岛屿数量C++题解,精美图例和流程图,一题带你弄懂图的dfs遍历算法
    leetcode200.岛屿数量给你一个由‘1’(陆地)和‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。示例1:输入:grid=[[“1”,“1”,“1”,......
  • 代码随想录算法训练营day04之字符串
    题目及链接:344.反转字符串541.反转字符串||卡码网54.替换数字151.翻转字符串里的单词卡码网55.右旋字符串28.找出字符串中第一个匹配项的下标459.重复的子字符串344.反转字符串太简单就不写了541.反转字符串||题意:给定一个字符串s和一个整数k,从字符串开头算起,每......
  • 空域滤波算法
    空域滤波算法是图像处理中用于去除噪声的一类方法,它们直接在图像的像素坐标系中操作,通过分析图像中像素与周围像素的关系来去除噪声。以下是几种常见的空域滤波算法的原理描述及其在MATLAB中的实现代码。  1.均值滤波均值滤波是一种简单的线性滤波方法,它通过替换图像中每个......
  • 可用于机器学习的排列组合枚举算法含passcal - c shap-c源码
    可用于机器学习的排列组合枚举算法含passcal-cshap-c源码1机器学习和数据挖掘• 特征选择:在机器学习中,需要从多个特征中选择最有价值的组合。通过枚举不同的特征组合,可以找到最佳的特征集合。• 超参数优化:在训练模型时,需要调整多个超参数。通过枚举不同的超参数组......
  • 图像降噪算法概述
    图像降噪是图像预处理中非常重要的一步,旨在去除图像中的噪声,以提高图像质量并为后续的图像分析提供更好的基础。图像降噪算法可以根据其原理和技术进行分类,主要包括以下几个大类:1.空域滤波方法这些方法直接在像素级别上操作,通常涉及邻域内像素值的加权平均。均值滤波:简单地......
  • c++递归算法较难题:分解数字
    题目描述:输入自然数 n,然后将其分拆成由若干数相加的形式,参与加法运算的数可以重复,要求输出降序排列。输入描述:一个待拆分的自然数n,(n≤50) 。输出描述:若干个拆分的加法等式。样例输入:5样例输出:5=55=4+15=3+25=3+1+15=2+2+15=2+1+1+15=1+1+1+1+1题目思想:将要分......
  • C++回溯算法经典例题:四皇后问题
    问题简介:在一个4×4的棋盘上,任意两个皇后都不能处在同一行、同一列任意两个皇后都不能处在同一斜线上(主斜线、反斜线)。题目分析:1.假设第一个皇后在(1,1):    1)在x=3时会卡死            2)在x=4时会卡死        2.假设第一个皇后在(2,1): ......
  • 【高录用!Fellow 主讲!SPIE独立出版 | 往届均已EI检索】第四届先进算法与神经网络国际学
    第四届先进算法与神经网络国际学术会议(AANN2024)由中国石油大学(华东)及山东省可信人工智能生态数据开放创新应用实验室联合主办,会议将于2024年8月9-11日在中国·青岛召开。AANN2024将围绕“先进算法与神经网络”的最新研究领域,为来自国内外高等院校、科学研究所、企事业......