C语言【微项目11】—活动安排问题[求解元素最多的相容活动子集](采用贪心算法思想实现)

2021/12/12 17:19:50

本文主要是介绍C语言【微项目11】—活动安排问题[求解元素最多的相容活动子集](采用贪心算法思想实现),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 一、Txsf.c
  • 二、 运行结果示例
    • 2.1 输入8个活动
    • 2.2 输入9个活动

【TDTX】
【C99】
【注】相容活动:两活动之间可顺序化,即两个需要执行的时间段无重叠
如:活动A:开始点0,结束点3;活动B:开始点1,结束点6;则两活动不相容,有重叠时间段。

一、Txsf.c

#include <stdio.h>
#include <stdlib.h>
struct hd
{
	int inorder;//活动输入顺序 
	int start;
	int end;
};

int kx(const void* q,const void* p)
{

	 	//printf("%d %d\n",((struct hd*) q)->end,((struct hd*) p)->end); 
	 	return ((struct hd*) q)->end - ((struct hd*) p)->end;
}

int main()
{
	int n;
	int i;
	printf("输入活动个数n:");
	scanf("%d",&n);

	struct hd mhd[n];//C99

	for(i = 0;i < n;i++)
	{
		printf("输入第%d个活动-开始点与结束点:",i+1);
		scanf("%d %d",&(mhd[i].start),&(mhd[i].end)); 
		mhd[i].inorder = i+1;
	}
	qsort(mhd,n,sizeof(mhd[0]),kx);//stdlib中的qsort()函数,给mhd[n]结构体数组排序 

	puts("\n依照活动的结束时间点,按非递减快速排序所有活动,得到活动顺序为:"); 
	for(i = 0;i < n;i++)
	{
		printf("活动%d(开始-%d,结束-%d)\n",mhd[i].inorder,mhd[i].start,mhd[i].end);
	}

	int B[n];
	for(i = 0;i < n;i++)
	{
		//将B[n]数组全部初始化为-1
		B[i] = -1;
	}

	int tend = -1;
	int k = 0;

	tend = mhd[0].end;
	B[0] = 0;

	puts("\n按照贪心算法所得活动执行顺序集合为:\n");

	puts("1.一边选择活动一边输出该元素:");
	printf("\n活动%d",mhd[0].inorder);

	for(i = 0;i < n;i++)
	{
		if( tend <= mhd[i].start )
		{
			B[k++] = i;//记录被选中活动在排序后mhd[n]数组中的位置 
			printf("-活动%d",mhd[i].inorder);

			tend = mhd[i].end;
		}
	}

	puts("\n");

	puts("2.通过记录数组B[n]输出结果:");
	printf("\n活动%d",mhd[0].inorder);
	for(i = 0;i < n;i++)
	{
		if(B[i] == -1)
		{
			break;
		}
		printf("-活动%d",mhd[B[i]].inorder);
	 }

	puts("");
	system("pause");
	return 0;
}

二、 运行结果示例

2.1 输入8个活动

8
3 6
1 3
5 9
0 2
7 9
9 12
9 11
12 14
在这里插入图片描述

2.2 输入9个活动

9
3 6
1 3
5 9
0 2
7 9
9 12
9 11
12 14
2 5
在这里插入图片描述


------------------------------------------------------第十一次发项目类文章有点激动啊!-----------------------------------------------------
-----------------------------------------------------【C语言—微项目—自编练习】----------------------------------------------------------
----------------------------------------------------------------【TDTX】--------------------------------------------------------------------------



这篇关于C语言【微项目11】—活动安排问题[求解元素最多的相容活动子集](采用贪心算法思想实现)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程