贪心算法

t = [100,50,20,5,1]

def change(t,n):
    m = [0 for _ in range(len(t))]
    for i,money in enumerate(t):
        m[i] = n//money
        n = n % money
    return m,n

print(change(t,376))

goods = [(60,10),(100,20),(120,30)]  #总价 重量
goods.sort(key=lambda x:x[0]/x[1],reverse=True) #按均价排序
print(goods)

def fractional_backpack(goods,w):
    m = [0 for _ in range(len(goods))]      #生成临时列表[0, 0, 0]
    print(m)
    total_v=0                               #背包里的价值
    for i,(price,weight)in enumerate(goods):
        if w > weight :                     #
            m[i] = 1
            total_v += price
            w -= weight
        else:
            m[i] = w / weight
            total_v += m[i]*price
            w=0
            break
    return m

print(fractional_backpack(goods,50))

三、活动最优方案

学校的大学生艺术中心周日将面向全校各个学院的学生社团开放，但活动中心同时只能供一个社团活动使用，并且每一个社团活动开始后都不能中断。现在各个社团都提交了他们使用该中心的活动计划（即活动的开始时刻和截止时刻）。请设计一个算法来找到一个最佳的分配序列，以能够在大学生艺术中心安排不冲突的尽可能多的社团活动。

activities = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
#保证活动是按照结束时间排序的
activities.sort(key=lambda x : x[1])

def activity_selection(a):
    res = [a[0]]                     #取最早结束的活动
    for i in range(1,len(a)):
        if a[i][0]>=res[-1][1] :     #当前活动开始时间>上个活动结束时间
            res.append(a[i])

    return res

print(activity_selection(activities))