Advertisement
jules0707

fractional_knapsack

Jun 20th, 2017
228
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.29 KB | None | 0 0
  1. # Uses python3
  2. import sys
  3.  
  4.  
  5. def get_optimal_value(capacity, weights, values):
  6.     value = 0
  7.     # amounts = []
  8.  
  9.     ratios = [values[i]/weights[i] for i in range(n)]
  10.  
  11.     # we repeat n times
  12.     for _ in range(n):
  13.         if capacity == 0:
  14.             return value
  15.  
  16.         # we select the maximum of the ratios index left ie. the one with some non null weight
  17.         max_ratio = max([ratios[i] for i in range(n) if (weights[i] > 0)])
  18.         # we retrieve the index index of that maximum ratio
  19.         max_index = ratios.index(max_ratio)
  20.         # then we calculate the maximum amount we can fill up the bag with
  21.         amount = min(capacity, weights[max_index])
  22.         # update the total value of that amount
  23.         value += amount*values[max_index]/weights[max_index]
  24.         # reduce the weight and write how much we put in
  25.         weights[max_index] -= amount
  26.         # amounts.append(amount)
  27.         # finally we update the capacity of the bag
  28.         capacity -= amount
  29.     return value
  30.  
  31.  
  32. if __name__ == "__main__":
  33.     data = list(map(int, sys.stdin.read().split()))
  34.     n, capacity = data[0:2]
  35.     values = data[2:(2 * n + 2):2]
  36.     weights = data[3:(2 * n + 2):2]
  37.     opt_value = get_optimal_value(capacity, weights, values)
  38.     print("{:.10f}".format(opt_value))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement