贪心算法之活动安排问题C语言代码_贪心算法活动安排问题c语言-程序员宅基地

技术标签: 算法  c语言  贪心算法  

贪心算法之活动安排问题C语言

  1. 问题描述
    该问题要求高效地安排一系列争用某一公共资源的活动。
    n:活动的个数,其中每个活动都要求使用同一资源,如演讲会场等。而且在同一时间内只有一个活动能使用这一资源。
    i:第i个活动
    S[]:存放各个活动开始时间的数组
    F[]:存放各个活动结束时间的数组
    A[]:存放结果的数组,为0,1值,A[i]为1代表活动i可以使用资源

  2. 问题分析
    相容:Si>=Fj或者Sj>=Fi,即第i个活动的开始时间大于等于第j个活动的结束时间,或者第j个活动的开始时间大于等于第i个活动的结束时间,那么就称活动i和活动j是相容的,即不冲突的。活动安排问题中就是要在所给的活动集合中选出最大的相容活动子集合。
    在这个问题中,贪心算法的体现就是每次总是选择具有最早结束时间的相容活动。因此这就要求我们要对结束时间进行排序,要求为非减序列。
    但是在排序的时候我们应该注意,不能对F,S数组进行位置变换,因为我们输入的时候活动是有顺序的,恰好用数组的下标来表示,从1~n,如果我们在排序的时候换了位置,那么活动的顺序就乱了(我是这样想的,可能有其他解决办法),所以在这里我定义了数组t[N]用来存放结束时间从小到大的下标。根据下标来进行下一步的贪心选择。

  3. 代码

#include <stdio.h>
#define N 15

void sort(int S[],int F[],int n);
void arrange(int S[],int F[],int n);
int A[N]={
    0};
int t[N]={
    0};

void sort(int S[],int F[],int n)
{
    
        int i,j;
        for(j=1;j<=n;j++)       //对结束时间进行排序
        {
    
                for(i=1;i<n;i++)   //有点类似冒泡排序
                {
    
                        if(F[t[i]]>F[t[i+1]])   //这里用t[i]而不直接用i是因为F>数组中的数据并没有交换,用t[i]存储的下标来进行索引
                        {
    
                                int temp = t[i];
                                t[i] = t[i+1];
                                t[i+1] = temp;
                        }
                }
        }
}

void arrange(int S[],int F[],int n)
{
    
        int i,j=1;
        int a,b;
        A[t[1]] = 1;      //t[1]是结束时间最早的,会被选择
        a = t[j];         //a的作用是暂存,t数组中存放的是排序后的下标
        for(i=2;i<=n;i++)
        {
    
                if(F[a]>S[t[i]])   //如果结束时间大于第t[i]个的开始时间
                {
    
                        A[t[i]] = 0;
                }
                else
                {
    
                        A[t[i]] = 1;
                        a = t[i];  //这里如果是t[j],那么赋值后t数组会变乱,因>此用a暂存
                }
        }
}

int main(void)
{
    
        int S[N]={
    0},F[N]={
    0};
        int n,i;
		printf("请输入活动的个数:");
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
    
                t[i] = i;     //t[i]初始化,没排序之前
                printf("请输入第%d个活动的开始时间和结束时间:",i);
                scanf("%d %d",&S[i],&F[i]);
        }

        sort(S,F,n);
        arrange(S,F,n);

        for(i=1;i<=n;i++)
        {
    
                if(A[i]==1)
                        printf("%d ",i); //输出可以使用资源的活动
        }
        printf("\n");

        for(i=1;i<=n;i++)
        {
    
                printf("%d ",t[i]);      //排序后的结果
        }
        printf("\n");
        return 0;
  1. 结果
    那书上的一个例子做的测试
    第一行结果是要安排的活动(缺点:没有对活动顺序进行处理)
    第二行结果是按结束时间排序后的结果
    第三行结果就是数组A中存储的结果

  2. 感觉自己写的很麻烦,有点繁琐,效率好像也不是很高,希望可以改进,记录一下吧,改了一下午的代码┭┮﹏┭┮,仅供参考。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45713237/article/details/121443286

智能推荐

Java 1.8(圆的面积和周长)编写程序,使用以下公式计算并显示半径为5.5的圆的面积和周长。_java程序 已知圆的半径是5.6-程序员宅基地

文章浏览阅读2.1k次,点赞6次,收藏7次。package Try;import java.util.Scanner;//在java.util中导入Scanner包public class Circle { public static void main(String[] args) { System.out.println("请输入圆的半径");//友情提示 Scanner input = new Scanner(System.in);//创建一个名为input的输入环境 ._java程序 已知圆的半径是5.6

华为鸿蒙开发者大会什么时候召开,鸿蒙2.0来了!华为正式公布开发者大会时间:9月10日...-程序员宅基地

文章浏览阅读416次。原标题:鸿蒙2.0来了!华为正式公布开发者大会时间:9月10日8月2日晚上8点,华为通过官方微博正式对外宣布了华为开发者大会HDC2020的召开时间为9月10日至12日。这一消息与此前爆料的华为将于9月11日召开开发者大会的消息基本吻合。 不出意外的话,这场开发者大会的重头戏,将会是备受期待的鸿蒙2.0操作系统。因为按照去年华为开发者大会公布的鸿蒙系统应用时间表,今年华为将会上马鸿蒙2.0操作系统..._7月8鸿蒙鲲鹏大会什么时候召开

批量栅格投影(arcpy)_arcpy 摨西蓮銝箇掖-程序员宅基地

文章浏览阅读3.2k次,点赞3次,收藏20次。栅格投影的意义:将分辨率单位为度的变为米定义投影的意义:将某个栅格的坐标系变为想要的坐标系批量栅格投影的代码如下:# -*- coding: UTF-8 -*-#需要自行更改的如下:#inws:输入路径#outws:输出路径#Coordinate_System:目标投影坐标系import globimport osimport arcpy# 输入路径 应该注意,中文路径,会导致读不出文件inws = r"------"# 参考文件路径 使用栅格数据集(从其导入方形像元大_arcpy 摨西蓮銝箇掖

《Malware Analysis and Detection Engineering》第一章:恶意软件趋势与反病毒人员架构-程序员宅基地

文章浏览阅读279次。malspam 垃圾邮件_malware analysis and detection engineering

JavaEE--spring(4)_javaee配置异常通知-程序员宅基地

文章浏览阅读111次。AOPAOP:全称是 Aspect Oriented Programming 即:面向切面编程。简单的说它就是把我们程序重复的代码抽取出来,在需要执行的时候,使用动态代理的技术,在不修改源码的基础上,对我们的已有方法进行增强。AOP的作用及优势:作用: 在程序运行期间,不修改源码对已有方法进行增强。优势: 减少重复代码 提高开发效AOP的实现方式:使用动态代理技术AOP 相关术语Joinpoint(连接点): 所谓连接点是指那些被拦截到的点。在 spring 中,这些点指的_javaee配置异常通知

ValueError: not enough values to unpack (expected 3, got 2)-程序员宅基地

文章浏览阅读1.1w次,点赞4次,收藏4次。python报错:ValueError: not enough values to unpack (expected 3, got 2)分析:这个错误的信息是,期望有三个返回值,但其实函数只有两个返回值解决方法,检查函数和接收函数返回值的参数个数是否一致,改成一致即可..._valueerror: not enough values to unpack (expected 3, got 2)

随便推点

[kuangbin带你飞]专题一 简单搜索 K - 迷宫问题-程序员宅基地

文章浏览阅读87次。K - 迷宫问题定义一个二维数组: int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0,};它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。Input一个5 × 5...

解决SQL Server 2014 Management Studio无法将excel数据导入数据库_标题: sql server 导入和导出向导 ----------------------------程序员宅基地

文章浏览阅读1.2k次。标题: SQL Server 导入和导出向导------------------------------操作无法完成。------------------------------其他信息:未在本地计算机上注册“Microsoft.ACE.OLEDB.12.0”提供程序。 (System.Data)针对上面这个问题,可以尝试下载安装AccessDatabaseEngine.e..._标题: sql server 导入和导出向导 ------------------------------ 操作无法完成

无法获得 VMCI 驱动程序的版本: 句柄无效_visual machine communication interface(vmci)驱动程序-程序员宅基地

文章浏览阅读1.6k次。今天打开虚拟机遇到了一些问题,一直在网上查也没用,最后十分粗暴的重装了一遍。安装后打开的时候遇到了这个问题,查了一下解决了。在此记录一下。首先看一下VMCI。虚拟机交流接口VMCI(The Virtual Machine Communication Interface)是一个在一个或多个虚拟机与宿主机之间提供高速高效交流的基本组件(infrastructure)启用一个虚拟机的VMCI..._visual machine communication interface(vmci)驱动程序

(Python实用)用Python做的交互式动态大图_python pyecharts 动态放大-程序员宅基地

文章浏览阅读1.4k次。今天给大家分享1个pyecharts交互式动态可视化案例,通过先拆分、后组合的方式,一步步教你如何实现,具体成果如下。本次案例数据来源于国家统计局,通过爬虫获取,这里已给大家备好,请在文末获取一、绘制基本图形用pandas读取数据,通过整合数据格式,分别用pyecharts绘制地图、柱状图、饼图,具体内容如下:1.绘制地图importpyecharts.optionsasoptsfrompyecharts.globalsimportThemeTypefrompye..._python pyecharts 动态放大

LayUI upload上传组件上传文件的两种方式(手动上传、自动上传)_layui upload auto-程序员宅基地

文章浏览阅读8.3k次,点赞7次,收藏8次。1 手动上传上传文件分为两步,第一步选择文件,第二步上传文件。HTML代码:<input type='button' id='selectFile' value='选择文件'><div id='fileDiv'></div><input type='button' id='uploadFile' value='上传文件'>JS代码:$(function(){ initUpload();});//初始化上传组件funct_layui upload auto

CPU与外设之间的数据传送方式_cpu与外设采用无条件传送方式时,为保证传送数据的有效性,对外设有什么要求-程序员宅基地

文章浏览阅读2w次,点赞18次,收藏57次。在微型计算机系统中,CPU与外设之间的数据传送方式主要有程序传送方式、中断传送方式和直接存储器存取(DMA)传送方式,分别介绍如下。 7.2.1 程序传送方式 程序传送方式是指直接在程序控制下进行数据的输入/输出操作。程序查询方式分为无条件传送方式和查询方式(条件传送方式)两种。 一. 无条件传送方式 微机系统中的一些简单的外设,如开关、继电器、数码管、发光二极管等_cpu与外设采用无条件传送方式时,为保证传送数据的有效性,对外设有什么要求

推荐文章

热门文章

相关标签