首页 > 代码库 > 活动安排问题python实现
活动安排问题python实现
活动安排问题要求高效地安排一系列争用某一公共资源的活动,贪心算法提供了一个简单的方法,使尽可能多的活动能兼容地使用公共资源。贪心算法并不总能求得问题的整体最优解,但对于活动安排问题,贪心算法却能做到,使得最终所确定的相容活动集合的规模最大,证明不在这里给出。代码如下:
def greedyManage(meeting): length=len(meeting) meeting.sort(key=lambda x:x[1]) result=[False for i in range(length)] j=0 #当前选中的活动 result[j]=True #选中第一个活动 for i in range(1,length): if meeting[i][0]>=meeting[j][1]: j=i result[j]=True return result def show(result): length=len(result) print('安排的活动为:') count=0 for i in range(length): if result[i]: print('第',i+1,'个活动') count+=1 print('\n共计',count,'个活动') if __name__=='__main__': meetings=[(1,4),(3,5),(0,6),(5,7),(3,8),(5,9),(6,10),(8,11),(8,12),(2,13),(12,14)] res=greedyManage(meetings) show(res)
meetings是一个list,里面每个tuple是一个活动的起始时间和结束时间,刚开始是乱序的,首先要按照每个活动的结束时间升序排列,然后首先默认选择第一个活动,依次遍历所有活动找出相容的活动,最后输出结果如下:
转载请注明:转自http://blog.csdn.net/littlethunder/article/details/26449245
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。