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

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

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

看经典题目“活动安排问题”学贪心算法,还是不太清楚一些细节:
如题:
设有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条回答 默认 最新

  • CSDN专家-link 2022-10-13 08:19
    关注

    贪心算法只能求局部最优解。这个代码只是求得从第一个活动开始情况下的最优解而已

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

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

悬赏问题

  • ¥15 关于#matlab#的问题:在模糊控制器中选出线路信息,在simulink中根据线路信息生成速度时间目标曲线(初速度为20m/s,15秒后减为0的速度时间图像)我想问线路信息是什么
  • ¥15 banner广告展示设置多少时间不怎么会消耗用户价值
  • ¥16 mybatis的代理对象无法通过@Autowired装填
  • ¥15 可见光定位matlab仿真
  • ¥15 arduino 四自由度机械臂
  • ¥15 wordpress 产品图片 GIF 没法显示
  • ¥15 求三国群英传pl国战时间的修改方法
  • ¥15 matlab代码代写,需写出详细代码,代价私
  • ¥15 ROS系统搭建请教(跨境电商用途)
  • ¥15 AIC3204的示例代码有吗,想用AIC3204测量血氧,找不到相关的代码。