526互联

贪心算法--背包问题--分数背包

发布时间 2023-08-18 23:09:58作者: zylyehuo

博客地址：https://www.cnblogs.com/zylyehuo/

# -*- coding: utf-8 -*-

stuffs = [(60, 10), (100, 20), (120, 30)]  # 每个商品元组表示(价格, 重量)
stuffs.sort(key=lambda x: x[0] / x[1], reverse=True)


def fractional_backpack(goods, w):
    m = [0 for _ in range(len(goods))]
    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
            break
    return [total_v, m]


print("=========================分数背包问题=========================")
print(f"共{fractional_backpack(stuffs, 50)[0]}元，各买{fractional_backpack(stuffs, 50)[1]}")
print("============================================================")