Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Uses python3
- import sys
- def get_optimal_value(capacity, weights, values):
- value = 0
- # amounts = []
- ratios = [values[i]/weights[i] for i in range(n)]
- # we repeat n times
- for _ in range(n):
- if capacity == 0:
- return value
- # we select the maximum of the ratios index left ie. the one with some non null weight
- max_ratio = max([ratios[i] for i in range(n) if (weights[i] > 0)])
- # we retrieve the index index of that maximum ratio
- max_index = ratios.index(max_ratio)
- # then we calculate the maximum amount we can fill up the bag with
- amount = min(capacity, weights[max_index])
- # update the total value of that amount
- value += amount*values[max_index]/weights[max_index]
- # reduce the weight and write how much we put in
- weights[max_index] -= amount
- # amounts.append(amount)
- # finally we update the capacity of the bag
- capacity -= amount
- return value
- if __name__ == "__main__":
- data = list(map(int, sys.stdin.read().split()))
- n, capacity = data[0:2]
- values = data[2:(2 * n + 2):2]
- weights = data[3:(2 * n + 2):2]
- opt_value = get_optimal_value(capacity, weights, values)
- print("{:.10f}".format(opt_value))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement