Python写01背包问题代码贪心算法
时间: 2024-01-29 07:52:25 浏览: 17
好的,以下是Python实现01背包问题的贪心算法代码:
def fractional_knapsack(value, weight, capacity):
"""Return maximum value of items and their fractional amounts.
(max_value, [0/1, ...]) is returned where max_value is the maximum value of
items with total weight not more than capacity.
value[i]/weight[i] is the value per unit of weight of item i.
capacity is the maximum weight.
weight must be a list of integers.
value must be a list of integers.
capacity must be an int.
"""
index = list(range(len(value)))
# get value per unit weight in list
ratio = [v/w for v, w in zip(value, weight)]
# index is sorted according to value per unit weight in decreasing order
index.sort(key=lambda i: ratio[i], reverse=True)
max_value = 0
fractions = [0]*len(value)
for i in index:
if weight[i] <= capacity:
fractions[i] = 1
max_value += value[i]
capacity -= weight[i]
else:
fractions[i] = capacity/weight[i]
max_value += value[i]*capacity/weight[i]
break
return max_value, fractions
请问是否还有其他问题需要回答呢?