贪心算法（求最优解）

练习： 一：硬币找零

def grt_main(a):
    coins=[1,5,10,25,100]#制定硬币值
    result=[]#存储结果
    s_coins=sorted(coins,reverse=True)#进行从大到小排序
    for i in s_coins :
        #求硬币个数
        num_coin=int(a/i)
        result += [i]*num_coin
        #剩下的数值
        a=a-i*num_coin
        if a <= 0 :
            break
    return result

if __name__ == __main__:
    print(grt_main(36))

现象： 二：有一个贼在偷取一家商店时，发现n个物品，第i个物品价值v元，重w磅，他希望带走东西越多越好，但背包中只能装下w磅东西，（v,w为整数) 应该带走那几样东西？w=4kg （琴 2kg 4100 :手机 1kg 2000 ：电视 3kg 6000元 ：玩具 2kg 2100 ：书 0.2kg 800）

def grt():
    coins=[
        [2,4100],[1,200],[3,6000],
        [1,2100],[0.2,800]
    ]#制定物价
    bag=4#包存储能力
    bag1=[]
    many = 0 #获取总价值
    for i in range(len(coins)):
        price =  coins[i][1] / coins[i][0]
        coins[i].append(price)
    coins.sort(key=lambda coins : coins[2],reverse=True)#按性价比进行比较排序
    for data in coins :

        if data[1] <= bag :

            many += data[1]
            bag -= data[0]

        else:
            many += data[2]*bag #获取一部分
            bag1.append(data[0])
            break
    return many,bag1
print("价值：",grt())

任务规划 1，对元素进行排序 2，从任务集合中选择出满足条件的任务加入到目标集合（删除所以与目标冲突的集合。 3，从任务集合中选择结束时间最早的加入目标集合（直到任务集合为0）