算法導論,貪心算法 —— 活動選擇問題（python示例）

# coding=utf-8
# 疊代貪心算法  最大活動相容子集
def greedActSel(s,f):
    n = len(s)
    A = [1]
    k = 1
    for m in range(2, n):
        if s[m] >= f[k]:
            A.append(m)
            k = m
    return A


s = [0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, ]
f = [0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16, ]
print("======== 疊代方法 =======")
print(greedActSel(s, f))


# 遞歸貪心算法
def recuActSel(s, f, k, n):
    m = k + 1
    while m < n and s[m] < f[k]:
        m = m + 1
    if m < n:
        A.append(m)
        recuActSel(s, f, m, n)
    else:
        return


A = []
recuActSel(s, f, 0, len(s))
print("======== 遞歸方法 =======")
print(A)      

轉載于:https://my.oschina.net/xiaohuoer1995/blog/1600194