算法导论第五章概率分析和随机算法----Python实现

# 雇佣问题

def hire_assistant_random_place(A, mid_price=100):  # 中介费默认为100元
    best = 0
    n = len(A)
    price = 0
    for i in range(n):
        j = np.random.randint(i, n, size=1)[0]  # 均匀随机
        temp = A[i]
        A[i] = A[j]
        A[j] = temp
    for x in A:
        if x > best:
            price = price + mid_price + best  # 辞掉旧的费用
            best = x  # 雇佣
    return price


price_sum = 0
for i in range(10):
    A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]  # 最坏情况
    price = hire_assistant_random_place(A)
    price_sum += price
print("平均费用：", price_sum//10)