"""
活动安排问题(算法导论)-贪心算法
1.问题:
假定有一个n个活动的集合S={a1,a2,...,an}, 这些活动使用相同的资源(例如一个阶梯教室)，
而这些资源在某个时刻只能供一个活动使用. 每个资源都有以个开始时间si和结束时间fi且0<=si<fi.
求最大兼容活动集(活动ai和活动aj满足[si,fi)和[sj,fj)不重叠)
即: 所求的是一个原本全集的子集
2.子问题:
令Aij是所求Sij的最优解, 包含活动ak, 最优解包含活动ak,则得到两个子问题:
Sik和Skj 所求 Aij=Aik U {ak} U Akj
3.贪心选择
选择一个活动使得选出它后, 剩下的资源能被尽量多的其他任务所用.
直觉: 选择S中最早结束的活动, 因为它剩下的资源可供它之后尽量多的活动使用.
令Sk={ai属于S:si>=fk}为在ak结束后开始的任务集合, 做出贪心选择(选出a1)后, 剩下的S1是唯一
需要求解的子问题.
"""
L = []
def activity1(s, f, k, n):
"""
递归贪心算法
:param s: list[], 活动开始的时间
:param f: list[], 活动结束的时间
:param k: k, 指出要求解的子问题Sk
:param n: 问题规模n
:return: 返回Sk的一个最大兼容活动集
"""
m = k + 1
while m <= n and s[m] < f[k]:
m = m + 1
if m <= n:
L.append(m)
activity1(s, f, m, n)
return L
else:
return
def activity2(s, f):
n = len(s)
result = [1]
k=1
tempList = list(range(n))
tempList = tempList[2:]
for m in tempList:
if s[m] >= f[k]:
result.append(m)
k = m
return result
#print(activity1([0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12], [0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16], 0, 11))
print(activity2([0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12], [0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16]))
'''
结果:[1,4,8,11]
详细过程讲解参考算法导论
'''
贪心算法-活动安排问题
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
