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 = *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