cdsn_Python 2022-10-13 00:14 采纳率: 69%
浏览 22
已结题

对“活动安排问题”贪心法的问题

问题遇到的现象和发生背景

看经典题目“活动安排问题”学贪心算法,还是不太清楚一些细节:
如题:
设有n个活动的集合 E = {1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。

  每个活动 i 都有一个要求使用该资源的起始时间 si 和一个结束时间 fi,且 si < fi。如果选择了活动i,则它在半开时间区间 [si ,fi ) 内占用资源。若区间 [si , fi )与区间 [sj, fj ) 不相交,则称活动i与活动j是相容的。当 si ≥ fj 或 sj ≥ fi 时,活动 i 与活动 j 相容。

  活动安排问题就是在所给的活动集合中选出最大的相容活动子集合。

用代码块功能插入代码,请勿粘贴截图
#include <iostream>   
 2 using namespace std;   
 3   
 4 #define NUM 50 
 5 
 6 void GreedySelector(int n, int s[], int f[], bool b[])  
 7 {
 8     b[1]=true;  //默认将第一个活动先安排 
 9     int j=1;    //记录最近一次加入b中的活动  
10   
11       //依次检查活动i是否与当前已选择的活动相容
12     for(int i=2;i<=n;i++)  
13     {  
14         if (s[i]>=f[j])  
15         {   
16             b[i]=true;  
17             j=i;  
18         }  
19         else  
20             b[i]=false;  
21     }  
22 }
23 
24 int main()  
25 {  
26     int s[] = {0,1,3,0,5,3,5,6,8,8,2,12};          //存储活动开始时间
27     int f[] = {0,4,5,6,7,8,9,10,11,12,13,14};      //存储活动结束时间
28     bool b[NUM];  //存储被安排的活动编号 
29      int n = (sizeof(s) / sizeof(s[0])) - 1;
30      
31     GreedySelector(n, s, f, b);
32     
33     for(int i = 1; i <= n; i++)      //输出被安排的活动编号和它的开始时间和结束时间 
34     {  
35         if(b[i]) cout << "活动 " << i << " :" << "(" << s[i] << "," << f[i] << ")" <<endl;  
36     }  
37     return 0;  
38 }  

我想要达到的结果

想问一下,为什么可以默认选择第一个活动。如果选择第一个活动会导致后续不合理的选择,那不应该放弃第一个活动吗,如果强行选择第一个活动不会产生错误吗。
希望能解答一下我的问题

  • 写回答

2条回答 默认 最新

      报告相同问题?

      相关推荐 更多相似问题

      问题事件

      • 系统已结题 10月22日
      • 已采纳回答 10月14日
      • 创建了问题 10月13日

      悬赏问题

      • ¥15 关于lwip的pbuf数据提取问题
      • ¥50 请求关于BBS数据集的资源分享
      • ¥15 设计一份接口自动化测试报告
      • ¥15 手机安装kali后ifconfig 提示错误
      • ¥15 用C++求矩阵的特征值
      • ¥30 求解答(自动忽略本括号内容)
      • ¥15 根据C语言小型成绩管理系统画一个流程图
      • ¥15 Javaweb的增删改查
      • ¥30 用eclipse和sqlserver做
      • ¥15 unity 发布 kinect 项目后失去焦点的问题