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

3.2_backpack_背包问题最先出现在Python成神之路。