<算法>贪心策略设计并解决会场安排问题

这篇具有很好参考价值的文章主要介绍了<算法>贪心策略设计并解决会场安排问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🎉 每个不曾起舞的日子都是对生命的辜负

🎉写在前面

期末考试邻近,为了更好的应对《算法设计与分析》这门课程,我把书上以及老师讲过的案例都详细的做一个重现及解剖,让你熟记每一个潜在的考点,希望能给大家帮助。


🎉目录

问题描述

 贪心策略

 算法设计

代码实现

选择结构体

随机输入会议

按结束时间排序

最终会议确定

结束语


问题描述

设有n个会议的集合C={1,2,…,n},其中每个会议都要求使用同一个资源(如会议室),而在同一时间内只能有一个会议使用该资源。每个会议i都有要求使用该资源的起始时间bi和结束时间ei,且bi < ei 。如果选择了会议i使用会议室,则它在半开区间[bi, ei)内占用该资源。如果[bi, ei)[bj , ej)不相交,则称会议i与会议j是相容的。会场安排问题要求在所给的会议集合中选出最大的相容活动子集,也即尽可能地选择更多的会议来使用资源。

 贪心策略

1、选择最早开始时间且不与已安排会议重叠的会议

2、选择使用时间最短且不与已安排会议重叠的会议

3、选择具有最早结束时间且不与已安排会议重叠的会议

这里我选取第三种方法 

 算法设计

设有11个会议等待安排,用贪心法找出满足目标要求的会议集合。这些会议按结束时间的非减序排列如表所示

11个会议按结束时间的非减序排列表:

<算法>贪心策略设计并解决会场安排问题

代码实现

#include <iostream>
#include "会场安排.h"
#define n 11
struct meeting{
	int B;//开始时间
	int E;//结束时间
};
using namespace std;
int main()
{
	meeting M[n] = { {8,11}, {8,12}, {2,13}, {12,14}, {1,4},
		           {3,5}, {0,6}, {5,7}, {3,8}, {5,9}, {6,10} };
	for(int i=0;i<n;i++)
		for(int j=0;j<n-i-1;j++)
			if (M[j].E > M[j + 1].E) {
				meeting T;
				T = M[j]; M[j]= M[j+ 1]; M[j+1]= T;
			}
	int allowedTime = 0;
	for (int i = 0,j=0; i < n; i++) {
		if (M[i].B > allowedTime) {
			j++;
			cout << "安排的第"<<j<<"个会议号是 " << i+1 <<" 此会议开始时间为:" << M[i].B 
				<<" 此会议结束时间是:" << M[i].E << endl;
			allowedTime = M[i].E;
		}
	}
}

选择结构体

定义meeting结构体,只设置会议开始时间B和结束时间E即可。

随机输入会议

n 为11

meeting M[n] = { {8,11}, {8,12}, {2,13}, {12,14}, {1,4},
                   {3,5}, {0,6}, {5,7}, {3,8}, {5,9}, {6,10} };

按结束时间排序

冒泡排序实现即可:

for(int i=0;i<n;i++)
        for(int j=0;j<n-i-1;j++)
            if (M[j].E > M[j + 1].E)

            {
                meeting T;
                T = M[j]; M[j]= M[j+ 1]; M[j+1]= T;
            }

这里的中间变量必须设置为 meeting 类型,以便于将会议的所有属性都交换

最终会议确定

int allowedTime = 0;
    for (int i = 0,j=0; i < n; i++) {
        if (M[i].B > allowedTime) {
            j++;
            cout << "安排的第"<<j<<"个会议号是 " << i+1 <<" 此会议开始时间为:" << M[i].B 
                <<" 此会议结束时间是:" << M[i].E << endl;
            allowedTime = M[i].E;
        }
    }

先将会议开始时间设置为0,只要把按结束时间升序排列的第一个大于0的开始时间加到第一个内容哦即可,随后将第一个会议的结束时间设置为allowedTime,产生下一个不与第一个会议时间冲突的会议;然后自己加点输出语句,美观的运行出来结果就好了。

<算法>贪心策略设计并解决会场安排问题

结束语

这算是贪心法第一个案例,也是比较好理解的一个案例,希望大家分析后都能有自己的收获,下篇博客再见,觉得好就鼓励鼓励博主吧文章来源地址https://www.toymoban.com/news/detail-472429.html

到了这里,关于<算法>贪心策略设计并解决会场安排问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【贪心算法】LeetCode2071:你可以安排的最多任务数目

    [二分查找]LeetCode2040:两个有序数组的第 K 小乘积 二分查找算法合集 给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成,需要的力量值保存在下标从 0 开始的整数数组 tasks 中,第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数

    2024年02月05日
    浏览(43)
  • 贪心算法问题实验:贪心算法解决TSP问题

    TSP问题是指旅行商问题,即给定一组城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中有着广泛的应用。 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最

    2024年02月03日
    浏览(42)
  • 【程序设计竞赛算法】背包问题——贪心法

    贪心算法是一种基于贪心策略的算法,它在每一步选择中都采取当前状态下的最优选择,以期望最终达到全局最优解。 背包问题是一个经典的组合优化问题,可以分为 0-1 背包问题和分数背包问题。其中,0-1 背包问题要求物品只能选择一次,而分数背包问题允许物品被选择多

    2024年02月03日
    浏览(41)
  • 区间图着色问题:贪心算法设计及实现

    在本文中,我们将探讨如何使用贪心算法解决一个特定的资源分配问题,即区间图着色问题。该问题可以描述为将一系列活动分配到最少数量的教室中,其中任意活动都可以在任意教室进行,但两个不兼容的活动不能安排在同一教室。我们将通过构造一个区间图来模拟这一问

    2024年04月27日
    浏览(38)
  • 算法题:摆动序列(贪心算法解决序列问题)

    这道题是一道贪心算法题,如果前两个数是递增,则后面要递减,如果不符合则往后遍历,直到找到符合的。(完整题目附在了最后) 代码如下: 完整题目: 376. 摆动序列 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为  摆动序列 。 第一个差(如果

    2024年02月07日
    浏览(58)
  • Java 贪心算法经典问题解决

    题目 一块金条切成两半,是需要花费和长度数值一样的铜板的。比如 长度为20的 金条,不管切成长度多大的两半,都要花费20个铜 板。一群人想整分整块金 条,怎么分最省铜板? 例如,给定数组{10,20,30},代表一共三个人,整块金条长度为 10+20+30=60. 金条要分成10,20,30三个部分

    2024年02月16日
    浏览(50)
  • 贪心算法解决多机调度问题

    一、问题描述         设有N个独立的作业{1,2,...,n},由M台相同的机器进行加工处理。作业i所需时间为Ti.约定:任何作业可以在任何一台机器上加工,处理单位完工前不允许中断处理,人和作业不能拆分成更小的作业 。要求给出一种作业调度方案,使所给的N个作业,在尽可能

    2024年02月11日
    浏览(38)
  • 算法设计 || 第5题:钓鱼问题-北京大学网站在线算法题(贪心算法)

    目录 (一)题目网址+视频网址  (二)手写草稿思考 Part1: 慕课PPT  Part2: 笨蛋的学习 北京大学网站在线算法题: 1042 -- Gone Fishing (poj.org) 视频讲解(北京大学附郭炜教授) : 程序设计与算法(二)算法基础_北京大学_中国大学MOOC(慕课) (icourse163.org) 老师的视频讲解,发现老

    2024年02月05日
    浏览(43)
  • python使用贪心算法解决作业调度问题

    对于作业调度问题,其实至今都还不能找到一个最优的解决方案,对与如何将任务和机器进行一个合理安排和分配,让其能够在最短时间内将所有任务全部完成,和计算机操作系统的任务调度过程相类似。 这里主要是给定n个作业和m台相同的机器,使用这些机器来对给定的作

    2024年01月20日
    浏览(38)
  • 贪心算法解决背包问题和动态规划解决0-1背包问题(c语言)

    运行结果如下: 运行结果如下: 总结: 贪心算法: 每一步都做出当时看起来最佳的选择,也就是说,它总是做出局部最优的选择。 贪心算法的设计步骤: 对其作出一个选择后,只剩下一个子问题需要求解。 证明做出贪心选择后,原问题总是存在最优解,即贪心选择总是安

    2024年02月04日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包