贪心算法解决问题（C语言）

• 前言
• 一、实验步骤及结果
• 总结

解决问题：
通过贪心法求解活动安排问题
【问题描述】假设有一个需要使用某一资源的11个活动所组成的集合S，S={1，…，11}。该资源任何时刻只能被一个活动所占用，活动i有一个开始时间bi和结束时间ei（bi 一旦某个活动开始执行，中间不能被打断，直到其执行完毕。若活动i和活动j有bi≥ej或bj≥ei，则称这两个活动兼容。
例如，对于下表的n=11个活动
设计算法求一种最优活动安排方案，使得所有安排的活动个数最多。

代码：

#include
#include

int n;
int b[100];
int e[100];
int cnt=0;
int B[100];
int E[100];

void solve();
void output();
void fun();

int main()
{   int j;
    memset(B,0,sizeof(B));
    memset(E,0,sizeof(E));
	printf("请输入活动的数量:n");
	scanf("%d",&n);
	fun();
	printf("请输入活动起始时间：n");
	for(j=0;j
		printf("请输入第%d个活动起始时间： ",j+1);
		scanf("%d",&b[j]);
	}
	fun();
	printf("请输入活动结束时间：n");
	for(j=0;j
		printf("请输入第%d个活动结束时间： ",j+1);
		scanf("%d",&e[j]);
	}
	fun();
	printf("活动名称：");
	for(j=0;j
		printf("%3d",j+1);
	}
	printf("n起始时间：");
	for(j=0;j
		printf("%3d",b[j]);
	}
	printf("n结束时间：");
	for(j=0;j
		printf("%3d",e[j]);
	}
	printf("n");
	fun();
    solve();
    output();
    return 0;
}
void solve()
{
    int i,j=0;
    B[0]=b[0];
    E[0]=e[0];
    for(i=0;i<=n;i++){
        if(b[i]>=e[j]){
            j=i;
            cnt++;
            B[cnt]=b[j];
            E[cnt]=e[j];
        }
    }
}
void output()
{
    int i;
    printf("求解结果为：n");
    printf("选取的活动为：n");
    for(i=0;i<=cnt;i++){
        printf("第%d个活动：[%d,%d]n",B[i],E[i]);
    }
    printf("n共选取%d个活动n",cnt+1);
}
void fun()
{
	printf("      ******************************************n");
}

结果如下：

本次实验较为简单实现，通过建立两个数组，分别记录起始时间和结束时间，通过设置贪心算法，即前个活动结束时间一定要小于后个活动开始时间进行挑选，在通过两个空数组进行放入，这大大减免了使用结构体的效率，通过全局变量和空数组来代替他们的效果，但同时由于改版少了用活动结束时间递增排序的效果，有利有弊，可以考虑使用之前学习的排序算法，这是该程序值得改进的方向。