c_cpp【贪心算法】活动安排问题(代码片段)

关键词：

//4d1 活动安排问题 贪心算法
#include "stdafx.h"
#include <iostream> 
using namespace std; 
 
template<class Type>
void GreedySelector(int n, Type s[], Type f[], bool A[]);
 
const int N = 11;
 
int main()

	//下标从1开始,存储活动开始时间
	int s[] = 0,1,3,0,5,3,5,6,8,8,2,12;
 
	//下标从1开始,存储活动结束时间
	int f[] = 0,4,5,6,7,8,9,10,11,12,13,14;
 
	bool A[N+1];
 
	cout<<"各活动的开始时间,结束时间分别为："<<endl;
	for(int i=1;i<=N;i++)
	
		cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
	
	GreedySelector(N,s,f,A);
	cout<<"最大相容活动子集为："<<endl;
	for(int i=1;i<=N;i++)
	
		if(A[i])
			cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
		
	
 
	return 0;

 
template<class Type>
void GreedySelector(int n, Type s[], Type f[], bool A[])

	A[1]=true;
	int j=1;//记录最近一次加入A中的活动
 
	for (int i=2;i<=n;i++)//依次检查活动i是否与当前已选择的活动相容
	
		if (s[i]>=f[j])
		 
			A[i]=true;
			j=i;
		
		else
		
			A[i]=false;
		
	

c++算法主题系列之贪心算法的贪心之术(代码片段)

...。本文将通过几个案例深入探讨贪心算法的贪心策略。2.活动安排问题问题描述：有n个活动a1,a2,…,an……需要在同一天使用同一个教室，且教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi。一个活... 查看详情

贪心算法-第一节：贪心算法概述(代码片段)

...题目描述②：解题思路③：完整代码（2）活动安排问题①：题目描述②：解题思 查看详情

python_分治算法贪心算法动态规划算法(代码片段)

...思想2、寻找假币示例二、贪心算法1、思想2、最大不相容活动安排示例三、动态规划1、思想2、最大和路径3、背包问题4、动态规划和贪心算法的区别一、分治算法思想分治算法是一种化繁为简的算法思想。分治算法往往应用于... 查看详情

数据结构与算法笔记（十七）——贪心算法及经典案例(找零问题背包问题拼接最大数字问题活动选择问题)(代码片段)

一、贪心算法贪心算法(又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法并不保证会得到最优... 查看详情

数据结构与算法笔记（十七）——贪心算法及经典案例(找零问题背包问题拼接最大数字问题活动选择问题)(代码片段)

一、贪心算法贪心算法(又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法并不保证会得到最优... 查看详情

贪心算法-活动安排问题(代码片段)

活动安排问题问题描述有n个需要使用同一资源的活动，且在同一时段只有一个活动能使用该资源。每个活动i都有一个起始时间si和结束时间fi，且si<ei。如果选择了活动i，则它在半开时间区间[si，ei)内占用资源。若区间[si，ei)... 查看详情

贪心算法回溯算法(代码片段)

...问题化简为一个更小的与原问题具有相同形式的子问题。活动安排问题回溯算法应用回溯法求解时，需要明确定义问题的解空间。旅行商问题–>使用排列数解决。用约束函数在扩展结点处剪去不满足约束条件的子树；... 查看详情

算法设计与分析贪心算法--活动安排问题

活动安排问题https://blog.csdn.net/qq_40452317/article/details/88875384贪心算法汇总--喷水装置问题、会场安排问题、过河问题https://blog.csdn.net/liujiuxiaoshitou/article/details/69728714 查看详情

活动安排问题-贪心算法

贪心算法：贪心算法总是做出在当前看来最好的选择，也就是贪心算法不从整体最优化的角度考虑。它所做出的选择只是在某种意义上的局部最优选择性质：最优子结构性质当一个问题的最优解包含其子问题的最优解... 查看详情

c_cpp第1周贪心(代码片段)

查看详情

贪心算法(贪婪算法)(代码片段)

贪心算法(贪婪算法)文章目录**贪心算法思想**选择排序平衡字符串买卖股票的最佳时机跳跃游戏钱币找零多机器调度问题举办活动数量最多无重叠区间贪心算法思想​1.贪心算法（又称贪婪算法）是指，在对问题求解... 查看详情

贪心算法(代码片段)

贪心策略　　总是做出当前做好的选择。　　贪心策略：将问题分成多个子问题；子问题求局部最优解；局部最优解组合成原问题的解。　　分类：简单贪心 区间贪心咖啡豆问题　题目描述FatMousepreparedMpoundsofcatfood,readytotrade... 查看详情

nyoj14-会场安排问题(贪心)(代码片段)

14-会场安排问题内存限制:64MB时间限制:3000msSpecialJudge:Noaccepted:9submit:15题目描述:学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动... 查看详情

背包问题（贪心算法）(代码片段)

...意：这是背包问题，而不是0-1背包问题，背包问题可以用贪心算法进行求解，但0-1无法用贪心算法求解，需要用动态规划算法求解；首先对贪心算法做一下总结，以及它与动态规划算法的区别：贪心算法两个最重要的性质：（1... 查看详情

贪心算法(代码片段)

Java实现贪心算法（找零钱问题）1packagecom.java;23importjava.util.Random;4/**5*贪心算法6*贪心算法，又称贪婪算法，是指在对问题求解时，总是做出在当前看来是最好的选择。7*也就是说，不从整体最优解出发来考虑，它所做出的仅是在... 查看详情

hdu2037今年暑假不ac(贪心，活动安排问题)(代码片段)

今年暑假不ACTimeLimit:2000/1000ms(Java/Other)   MemoryLimit:65536/32768K(Java/Other)TotalSubmission(s):15   AcceptedSubmission(s):13Font: TimesNewRoman | Verdan 查看详情

背包问题（贪心算法）(代码片段)

　　贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。　　贪心算法还是比较好理解的一个算法，以前我也... 查看详情

核心算法6贪心算法(代码片段)

贪心算法就是遵循某种既定原则，不断地选取当前条件下最优的选择来构造每一个子步骤的解决方案，直到获得问题最终的求解。在对问题求解时，总是做出在当前看最好的选择。也就是说，不从整体最优上考虑，所做的仅是在... 查看详情