Paste Search Dynamic
fractions
  1. def insertionSort(A,index):
  2.     for j in range(1,len(A)):
  3.         key = A[j]
  4.         key2 = index[j]
  5.         i=j-1
  6.         while i>=0 and key > A[i]:
  7.             A[i+1] = A[i]
  8.             index[i+1] = index[i]
  9.             i-=1
  10.         A[i+1] = key
  11.         index[i+1] = key2
  12.  
  13.  
  14. def fractional_knapsack(value, weight, capacity):
  15.  
  16.     index = list(range(len(value)))
  17.     ratio = [v/w for v, w in zip(value, weight)]
  18.     insertionSort(ratio,index)
  19.     max_value = 0
  20.     fractions = [0]*len(value)
  21.     for i in index:
  22.         if weight[i] <= capacity:
  23.             fractions[i] = 1
  24.             max_value += value[i]
  25.             capacity -= weight[i]
  26.         else:
  27.             fractions[i] = capacity/weight[i]
  28.             max_value += value[i]*capacity/weight[i]
  29.             break
  30.  
  31.     return max_value, fractions
  32.  
  33. n = int(input('Enter number of items: '))
  34. value = input('Enter the values of the {} item(s) in order: '
  35.               .format(n)).split()
  36. value = [int(v) for v in value]
  37. weight = input('Enter the positive weights of the {} item(s) in order: '
  38.                .format(n)).split()
  39. weight = [int(w) for w in weight]
  40. capacity = int(input('Enter maximum weight: '))
  41.  
  42. max_value, fractions = fractional_knapsack(value, weight, capacity)
  43. print('The maximum value of items that can be carried:', max_value)
  44. print('The fractions in which the items should be taken:', fractions)
Parsed in 0.012 seconds