背景

话说一个小偷在某商店发现有n个商品，第i个商品价值vi元，重wi千克。他希望拿走的价值尽量高，但他的背包最多只能容纳W千克的东西。他应该拿走哪些商品？

分数背包：对于一个商品，小偷可以拿走其中任意一部分。（ 唉，这年头，小偷也不好当了！）

 

思想

贪心思想：因为商品是可以被拆分来拿的，所以我们可以挑那些单位价值更贵的商品先拿，遇到整个商品拿不下的情况，我们就直拿一部分即可。

源码

def fractional_backpack(goods, W):
    '''
    :param goods:商品列表
    :param W: 背包可以容纳的重量
    :return: 拿走的最大价值
    '''

    # 对商品按照单位价值进行降序排序
    goods.sort(key=lambda a: a[0] / a[1], reverse=True)
    n = [0 for i in range(len(goods))]  # 记录每个商品取走多少

    for i, (price, weight) in enumerate(goods):
        # 贪心算法：每次总是先拿价值最大的商品
        if W > weight:
            n[i] = 1  # 如果背包的容量大于商品的重量，就可以全部取走
            W -= weight  # 拿走weight千克
        else:
            n[i] = W / weight  # 拿走W千克
            W -= W
            break
    res_li = [goods[i][0] * num for i, num in enumerate(n)]
    print(n)
    print(goods)
    print(res_li)
    return sum(res_li)

 同步更新于个人博客系统：贪心算法之分数背包