算法导论 贪心算法之活动选择问题

Posted on |

代码

贪心算法的递归实现 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
"""递归贪心算法"""
def recursive_activity_selector(s,f,k,n):
    m=k+1
    while m<n and s[m]<f[k]:
        m+=1
    if m<n:
        return [m]+recursive_activity_selector(s,f,m,n)
    else:
        return []
# if __name__=='__main__':
#     s = [-1,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('recursive:\t',recursive_activity_selector(s,f,0,len(s)))
#     print('non_recursive:\t',greedy_activity_selector(s,f))

贪心算法的迭代实现 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def greedy_activity_selector(s,f):
    assert len(s)==len(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
# if __name__=='__main__':
#     s = [-1,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('recursive:\t',recursive_activity_selector(s,f,0,len(s)))
#     print('non_recursive:\t',greedy_activity_selector(s,f))

动态规划的自底向上实现