计算参加系列讲座的最低学生人数
||
一些学生希望通过将最少数量的学生参加“ 0”场讲座中的每一个,来最大程度地减少他们的演讲出席率。
讲座
i
在时间time2ѭ开始并在时间b[i]
结束
从讲座ѭ1到讲座j
需要r[i][j]
的时间
有什么算法可以计算参加所有讲座所需的最少学生人数?
没有找到相关结果
已邀请:
1 个回复
栖很钾是狠
交流到讲座
,则在图中的节点对
之间构造边缘。图的\“ root \”节点是一天中的第一类(在其他任何类均及时结束以到达该类之前开始的类)。 第一个主要观察结果是该图是有向的和非循环的(您无法及时返回)。 您的目标是找到通过图形的最小路径数,以使每个节点至少被访问一次。这立即导致第二个关键发现,那就是这可以贪婪地完成。 因此,算法如下: 在有向无环图(DAG)中找到最长的路径 从图中删除在该路径中找到的节点 递增
重复直到图没有更多节点 使用动态编程可以很容易地在DAG中找到最长的路径: 计算图的拓扑阶
保持数组
和
个元素(图中的节点数),并初始化为
保留带有
个元素的数组
,将前一个节点存储在路径中 然后
您的最长路径以ѭ18结尾,因此最大为ѭ19。最长路径可以通过使用
数组从
回溯来计算。