精华内容
下载资源
问答
  • 活动安排
    2021-02-20 11:53:51

    问题描述

    设有n个活动,每个活动要求使用统一资源,每个活动i都有起始时间s和一个结束时间f,活动1执行完成后活动2也可以完全执行,则活动1与活动2相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。活动结束时间以升序排列。

    算法分析

    1.活动安排问题可以用贪心算法求解,从贪心算法的思想出发,总是作出当前最好的选择,并不需要从整体最优考虑,完成的是局部最优选择,整体最优解可以通过一系列局部最优的选择当然活动安排问题用贪心算法求解则是最优选择。

    2.基本思路

    一、建立数学模型来描述问题。

    二、把求解的问题分成若干个子问题。

    三、对每一子问题求解,得到子问题的局部最优解。

    四、把子问题的解局部最优解合成原来解问题的一个解。

    java 源代码:

    import java.util.Scanner;
    
    public class Greedy {
        public static void greedySelector(int []s,int[] t,boolean []a){
            a[0] = true;
            int j=0;
            int count=1;
            for (int i = 1; i <=s.length-1; i++) {
                if(s[i]>=t[j]){
                    a[i]=true;
                    j=i;
                    count++;
                }
                else a[i]=false;
            }
            System.out.println("活动个数:");
            System.out.println(count);
            System.out.println("活动顺序:");
            for (int i = 0; i < a.length; i++) {
                if (a[i]==true){
                    System.out.print(i+",");
                }
            }
        }
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);      //活动以结束时间升序排列
            System.out.println("输入活动个数:");
            int a = sc.nextInt();
            int[] f = new int[a];
            int[] g = new int[a];
            System.out.println("依次输入全部活动的开始时间:");
            for (int i = 0; i < a; i++) {
                f[i] = sc.nextInt();
            }
            System.out.println("依次输入全部活动的结束时间:");
            for (int i = 0; i < a; i++) {
                g[i] = sc.nextInt();
            }
            boolean [] b = new boolean[a];
            Greedy test = new Greedy();
            test.greedySelector(f,g,b);
        }
    }
    

    在这里插入图片描述

    复杂度分析

    贪心算法不是很复杂的算法,当输入的活动已按结束时间的升序排列,算法只需*O(n)的时间安排n个活动,使最多的活动能相容地使用公共资源。如果所给出的活动未非升序排列,可以用O(nlogn)*的时间重排。

    更多相关内容
  • 实验三 贪心法解活动安排问题 一实验内容及要求 1要求按贪心法求解问题 2要求读文本文件输入活动安排时间区间数据 3要求显示结果 二实验仪器和软件平台 仪器 普通电脑一台 软件平台 WIN-XP + MyEclipse 6.0 三源程序...
  • 实验九:活动安排问题(贪心算法)报告2017061111 李静娴1.问题描述设有 n 个活动的集合 E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动 i 都...
  • 本篇文章主要介绍了浅谈Python实现贪心算法与活动安排问题,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 活动安排问题的动态规划、贪心算法和树搜索算法求解。 比如有一个多媒体教室,现在有四个待举办活动A、B、C、D。A是在8:00到10:00举行,简单记为[8, 10];B是[12, 14];C是[15, 17];D是[11, 19]。为了让尽可能多的...
  • 小学语文教研活动安排表.pdf
  • 主要是使用贪心算法,实现活动安排的个数最多
  • 2020年小学阳光体育活动一小时工作计划及活动安排表.pdf
  • 活动安排问题

    2012-11-08 21:19:30
    用c++代码编程,基于贪心算法的思想,解决实现活动安排问题
  • 教育精品资料
  • Activearr.rar_活动安排

    2022-09-21 03:29:31
    用贪心算法编写的有关活动安排问题的java程序
  • 活动安排问题是利用贪心算法有效求解的很好例子。该问题要求高校的安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法,使尽可能多的活动可以兼容的使用某一公共资源
  • 对大型活动安排,贪心法,先对结束时间排序在依次取出最大子集。
  • 活动安排问题.rar

    2020-06-21 21:06:45
    哈工程算法课程中的二次实验 活动安排问题 包括代码,实验报告 . . . . . .
  • 学校关于“互联网+”大学生创新创业大赛线上推进活动安排.pdf学校关于“互联网+”大学生创新创业大赛线上推进活动安排.pdf学校关于“互联网+”大学生创新创业大赛线上推进活动安排.pdf学校关于“互联网+”大学生创新...
  • 学校关于“互联网+”大学生创新创业大赛线上推进活动安排.docx学校关于“互联网+”大学生创新创业大赛线上推进活动安排.docx学校关于“互联网+”大学生创新创业大赛线上推进活动安排.docx学校关于“互联网+”大学生...
  • 活动安排.doc

    2021-12-06 14:01:45
    活动安排.doc
  • 贪心算法之活动安排问题C语言代码

    千次阅读 2021-11-20 18:17:07
    贪心算法之活动安排问题C语言 问题描述 该问题要求高效地安排一系列争用某一公共资源的活动。 n:活动的个数,其中每个活动都要求使用同一资源,如演讲会场等。而且在同一时间内只有一个活动能使用这一资源。 i:...

    贪心算法之活动安排问题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. 感觉自己写的很麻烦,有点繁琐,效率好像也不是很高,希望可以改进,记录一下吧,改了一下午的代码┭┮﹏┭┮,仅供参考。

    展开全文
  • 贪心算法解决活动安排 问题 问题概述 分析问题 解决问题 编程 编程流程以及数据类型选择 发现问题以及解决 最终实现 总结 程序缺陷以及完善 解题心路历程 问题 问题概述 设有n个活动的集合E={1,2,...

    贪心算法解决活动安排

    问题

    问题概述

    分析问题

    解决问题

    编程

    编程流程以及数据类型选择

    发现问题以及解决

    最终实现

    总结

    程序缺陷以及完善

    解题心路历程


    问题


    问题概述

    设有n个活动的集合E={1,2,……,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i,则它在时间区间[si,fi]内占用资源。若区间[si,fi]与区间[sj,fj]不相交,则称活动i与活动j是相容的。也就是说,当si>=fj或者sj>=fi时,活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。


    分析问题

    通过问题概述,可以模拟一个场景:

    一个舞台在一天中是空闲的,可以用作活动的场合,不可以同时进行两个活动。所以活动的开始时间和结束时间是活动安排的判断标准。

    问题的答案以及目的,是让舞台得到充分利用,进行最多的活动,即求出进行最大的活动的个数。


    解决问题

    可以将申请场地的所有的活动进行非减序排列(非减序排列,即说明当两个活动的结束时间相同,可以进行并列)。

    定义两个集合,用于存储入选活动和候选活动。

    获得非减序排列的活动排序后,对于第一个的活动,直接进行选择。此时,第一个活动即是入选活动。其它的活动是候选活动,对活动的开始时间和结束时间进行比较。有以下几种情况:

    1. 入选活动集合的最后一个活动的结束时间大于候选活动集合的第1个活动的开始时间,那个这个候选活动即被淘汰出候选活动集合。
    2. 入选活动集合的最后一个活动的结束时间小于等于候选活动集合的第一个活动的开始时间,那么这个候选活动将被选择到入选活动集合中。

    重复以上操作,当候选活动集合没有活动时,则解决问题。以上的选择即是贪心选择,选择出当前的最优解。

    综上,问题的解决有两个大的部分,部分1是对活动进行非减序排序;部分2是对活动进行贪心选择。

     


    编程


    编程流程以及数据类型选择

    结合问题的部分,可以确定有以下步骤

    1. 通过键盘输入获得活动的开始时间和结束时间,使用元组存储活动的开始时间和结束时间,为活动元组;使用2个列表分别存储活动id、活动元组
    2. 根据活动的结束时间对活动进行非减序排列,并使用字典存储已经排序好的活动,字典的键对应活动的id,值对应活动元组。为候选活动字典
    3. 打印排序好的活动列表,打印活动字典
    4. 使用贪心算法对活动进行选择,使用字典存储入选活动的id和开始时间和结束时间,为入选活动字典
    5. 打印结果

    发现问题以及解决

    问题1:如何根据列表中元组元素的第二个参数进行排序,即对活动的结束时间进行排序

    解决:定义一个函数

    def takeSecond(elem):
        return elem[1]

    用于返回列表的每个元组的第2个元素,并使用内置函数sort对列表进行排序

    sort(key=takeSecond)

     


    最终实现

    程序代码:

    #proname:greedy_act
        #author:zhj
        #time:2019.10.29
        #language:python
        #version:1.0
    #arg:tuple=>(0,1)
    #return:tuple[1]=>1
    def takeSecond(elem):
        return elem[1]
    #arg:lst_id:[1,2,3,..,n]
    #    lst_act:[(s[1],f[1]),(s[2],f[2]),...,(s[n],f[n])]
    #return:sort of dict_act
    # {1:(,*),2:(,**),...,n:(,**n)}
    def sortAct(lst_id,lst_act):
        lst_sort_act = lst_act
        lst_sort_act.sort(key=takeSecond)
        dict_act = dict(zip(lst_id,lst_sort_act))
        return dict_act#test:success
    #arg:dict_act
    #{1:(,*),2:(,**),...,n:(,**n)}
    #return:gree of gree_act[id:(,*),id:(,**),...,id:(,*****)]
    def greedy(dict_act):
        true_id = []
        true_act = []
        #purpose: get the first to append the list
        true_ele_tuple = dict_act[1]
        true_id.append(1)
        true_act.append(true_ele_tuple)
        #purpose: get the  finish time of fist activity to divide element
        ele_divi = true_ele_tuple[1]
        for i in range(1,num_act):
    #get the first act finish time
            id = int(1+i)
            #purpose:get the seconde activity to the last activity
            tuple_ele_act = dict_act[id]
            #print(tuple_ele_act) #test:success
            if (tuple_ele_act[0] >= ele_divi):
                true_id.append(id)
                true_act.append(tuple_ele_act)
                ele_divi = tuple_ele_act[1]
        greedy_act = dict(zip(true_id,true_act))
        return greedy_act
    #main
    input_act = input("请输入活动的个数,n = ")
    num_act = int(input_act)
    print("请分别输入开始时间s[i]和结束时间f[j]:")
    lst_id = []
    lst_act = []
    for i in range(1,num_act+1):
        lst_id.append(i)
        input_start =eval(input("s["+str(i)+"]="))
        input_finish =eval(input("f["+str(i)+"]="))
        tuple = ()#purpose:def tuple to save the act_start and  act_finish
        tuple = (input_start,input_finish)
        lst_act.append(tuple)
        del tuple
        print("")
    dict_act = sortAct(lst_id,lst_act)
    print("按结束时间非减序排列如下:")
    print("序号----开始时间----结束时间")
    for i in range(1,num_act+1):
        id = int(i)
        ele_tuple = dict_act[i]
        print(id,"------",ele_tuple[0],"----------",ele_tuple[1])
    #test;success
    greedy_act = greedy(dict_act)
    #print(greedy_act)#test:success
    true_id = list(greedy_act.keys())
    # print(true_id)#test:success
    print("----------------------")
    print("安排的活动序号依次为:")
    printlen = len(true_id)
    for id in true_id:
          tuple_print = greedy_act[id]
          print(id,"    ",tuple_print[0],"------>",tuple_print[1])
    

    运行结果截图:

    总结


    程序缺陷以及完善

    • 缺陷:没有异常判断,可能出现输入异常等等异常;
      • 完善:可以进行增加的话,因为代码工作量不大
    • 无法打印所有的活动安排方案


    题目中是要求输出最多活动安排,所以也可以是另外一个方案。例如本题中,活动安排方案是 1->4->8->11,共4个活动。而2->4->8->11,1->4->9->11也是4个活动。

    • 完善:另一种处理方式,不只是贪心选择,而是将不符合的活动直接进行删除:第一个候选活动的开始时间小于最后一个入选活动的结束时间,那么这个候选活动,则直接进行删除
      • 例如本题中
        • 活动1已成功入选,那么活动2,3都直接删除
        • 活动4入选,同贪心选择,可以输出1->4->8->11
        • 回到第1步,删除活动4,则活动5直接删除;
        • 进行贪心选择,发现有1->6->11,存入列表,因为活动个数小于4,所以排除
        • 不断重复以上逻辑
      • 注:哪天有空,可以试试编写,并会在这里引用。
    • 代码优化:
      • 有很多代码可以进行优化,逻辑可以更加严密。

    解题心路历程

    使用贪心算法解决活动安排问题,可以说是对初学Python的一次有效的实践和应用。有以下几点需要笔记:

    • 使用正确的数据类型可以事半功倍:之前有尝试使用字典嵌套列表,结果发现处理流程,特别繁杂。所以使用字典嵌套元组,可以让问题处理逻辑更加清晰。减少大量的代码。
    • 程序逻辑清楚,可以使用函数优化代码,要明确每个函数的参数以及返回值是什么,以及这个函数的目的是什么

    本篇已完成编写,如有更改,会在此列出。

    展开全文
  • 实验三 活动安排 贪心1
  • Python编写的,利用贪心算法解决活动安排、哈夫曼编码、背包问题、最电路径、最优装载、最小生成树等问题
  • 活动安排的代码

    2014-03-15 18:41:41
    活动安排 C语言 代码 活动安排的代码
  • 贪心算大实现活动安排问题,算法实现使用图形界面动态显示,程序中用到的排序算法为快速排序
  • 贪心算法之活动安排问题

    千次阅读 多人点赞 2019-09-29 14:25:19
    活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动...

    活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。

    问题描述

    设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i,则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交,则称活动i与活动j是相容的。也就是说,当si≥fj或sj≥fi时,活动i与活动j相容。
    在这里插入图片描述

    问题求解

    活动安排问题的最优解是再所有活动集合中选出数量最多的相容活动子集合。若用贪心算法表示为:就是找出最早完成的活动,然后按照活动相容的条件依次往后寻找。这里能够发现:需要将所有活动按照结束时间进行非降序的排序,依次排列遍历找出最大的相容活动子集合。

    描述活动的数据结构:

    typedef struct{
       int s;//活动开始时间
       int f;//活动结束时间
       int index;//活动序号,视情况而定是否用上
    }action;
    

    根据活动的结束时间进行非降序排序:

    //根据活动结束时间进行非降序排序
    void sort_action(action a[],int n)
    {   int i,j;
        action temp;
        for(i=1;i<=n;i++)
        for(j=1;j<=n-i;j++)
        {
            if(a[j].f>a[j+1].f)
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    

    求解代码

    #include <iostream>
    #include<stdio.h>
    #include<stdlib.h>
    using namespace std;
    typedef struct{
       int s;//活动开始时间
       int f;//活动结束时间
       int index;//活动序号,视情况而定是否用上
    }action;
    //根据活动结束时间进行非降序排序
    void sort_action(action a[],int n)
    {   int i,j;
        action temp;
        for(i=1;i<=n;i++)
        for(j=1;j<=n-i;j++)
        {
            if(a[j].f>a[j+1].f)
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    
    int main()
    {
        int n;//输入n代表有n个活动
        cin>>n;
        action a[n+1];
        for(int i=1;i<=n;i++){
            cin>>a[i].s>>a[i].f;
            a[i].index=i;//构造活动结构体数组
        }
        sort_action(a,n);//冒泡排序
        bool b[n+1];
        int num=1;
        b[1]=true;//第一个活动必定安排
        int pretime=a[1].f;
        for(int i=2;i<=n;i++){
            if(a[i].s >= pretime){
                b[i]=true;
                num++;//a[i]活动安排上
                pretime=a[i].f;//更新pretime
            }else{
                b[i]=false;
            }
        }
        //输出相容的最大活动数目
        cout<<num<<endl;
        //根据情况是否输出活动序号
        for(int i=1;i<=n;i++){
            if(b[i]) cout<<a[i].index<<" ";
        }
        return 0;
    }
    

    在这里插入图片描述

    问题延伸

    现在问如果要把所有的活动全部安排上,请问最少需要几个活动场地。
    问题的实质就是:所有的活动集合能够划分成多少个最大相容的子集合,从而使所需要的活动场地最少。

    展开全文
  • printf("输入活动的个数:\n");printf("输入各个活动的开始和结束时间:\n");
  • 文章目录前言一、活动安排问题二、解题思路三、代码实现总结 前言 关于这个活动安排问题的解题思路我第一遍是真的没看懂,所以我就直接看代码了,没想到啊,过一遍代码就直接理解了,真神奇!所以啊,如果第二部分...
  • 代码中给出了用贪心法解决活动安排问题的集中方案。。用c++实现的,希望能给您帮助。
  • 贪心算法 活动安排问题.docx
  • 少先队每活动安排.docx
  • 少先队活动安排表.pdf

    2021-11-24 22:38:08
    少先队活动安排表.pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 127,748
精华内容 51,099
关键字:

活动安排

友情链接: MusicDoa.rar