贪心算法之背包问题
2021-06-03 17:01
标签：mic com 背包 break 排序 问题 src 分数 div 类别：1）0-1背包；2）分数背包 0-1背包使用贪心算法无法获得最优解 分数背包代码如下： 结果展示： 贪心算法之背包问题 标签：mic com 背包 break 排序 问题 src 分数 div 原文地址：https://www.cnblogs.com/demo-deng/p/14672467.htmldef 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))
