活动安排问题python实现
浏览数：22 /
时间：2015年06月08日
活动安排问题要求高效地安排一系列争用某一公共资源的活动，贪心算法提供了一个简单的方法，使尽可能多的活动能兼容地使用公共资源。贪心算法并不总能求得问题的整体最优解，但对于活动安排问题，贪心算法却能做到，使得最终所确定的相容活动集合的规模最大，证明不在这里给出。代码如下：
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
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
