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

贪心算法之活动安排问题C语言代码 2022-07-09 559

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

问题描述该问题要求高效地安排一系列争用某一公共资源的活动。 n：活动的个数，其中每个活动都要求使用同一资源，如演讲会场等。而且在同一时间内只有一个活动能使用这一资源。 i：第i个活动 S[]：存放各个活动开始时间的数组 F[]：存放各个活动结束时间的数组 A[]：存放结果的数组，为0，1值，A[i]为1代表活动i可以使用资源
问题分析相容：Si>=Fj或者Sj>=Fi，即第i个活动的开始时间大于等于第j个活动的结束时间，或者第j个活动的开始时间大于等于第i个活动的结束时间，那么就称活动i和活动j是相容的，即不冲突的。活动安排问题中就是要在所给的活动集合中选出最大的相容活动子集合。在这个问题中，贪心算法的体现就是每次总是选择具有最早结束时间的相容活动。因此这就要求我们要对结束时间进行排序，要求为非减序列。但是在排序的时候我们应该注意，不能对F,S数组进行位置变换，因为我们输入的时候活动是有顺序的，恰好用数组的下标来表示，从1~n，如果我们在排序的时候换了位置，那么活动的顺序就乱了（我是这样想的，可能有其他解决办法），所以在这里我定义了数组t[N]用来存放结束时间从小到大的下标。根据下标来进行下一步的贪心选择。
代码

#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("
");

        for(i=1;i<=n;i++)
        {
          
   
                printf("%d ",t[i]);      //排序后的结果
        }
        printf("
");
        return 0;