3.2_backpack_背包问题

--- 背包问题 ---
    综合考虑价格和重量

1. 分数背包
2. 0-1背包

 1. 分数背包

# (价值, 重量)
goods = [(60, 10), (100, 20), (120, 30)]
goods.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
            w = 0
            break
    return f'拿走 {m}，总价值: {total_v}'

 2. 0-1背包

tr = [None, {'w': 2, 'v': 3}, {'w': 3, 'v': 4}, {'w': 4, 'v': 8}, {'w': 5, 'v': 8}, {'w': 9, 'v': 10}]


def backpack_01(tr, max_w):
    """0-1背包"""

    # 初始化背包：前 i 个宝物中，最大价值为 w
    m = {(i, w): 0 for i in range(len(tr)) for w in range(max_w + 1)}

    for i in range(1, len(tr)):
        for w in range(1, max_w + 1):
            # 装不下第 i 个宝物，就不装
            if tr[i]['w'] > w:
                m[(i, w)] = m[(i - 1, w)]
            else:
                # 取最大值：不装第 i 个宝物 / 装第 i 个宝物
                m[(i, w)] = max(m[(i - 1, w)], m[(i - 1, w - tr[i]['w'])] + tr[i]['v'])

    return m[(len(tr) - 1, max_w)]