贪心算法之背包问题

类别：1）0-1背包；2）分数背包

0-1背包使用贪心算法无法获得最优解

分数背包代码如下：

def fractional_package(goods, w):
    """
    :param data: [(价值，重量),...]
    :param w:  要拿取的总重量
    :return:(拿走的数量，拿走的总价值)
    """
    goods.sort(key=lambda x:x[0]/x[1], reverse=True)    # 根据单位价值从大到小排序
    m = [0] * len(goods)
    total_value = 0
    for i, (price, weight) in enumerate(goods):
        if w >= weight:
            m[i] = 1
            total_value += price
            w -= weight
        else:
            m[i] = w / weight
            total_value += price * m[i]
            break
    return m, total_value

if __name__ == '__main__':
    data = [(100, 20), (60, 10), (120, 30)]
    print(fractional_package(data,70))

结果展示：