blob: 898d8daaaf03b436fdaf4a28a0f92e2375098846 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
# Uses python3
import sys
def getBestItem(values, weights):
maxValueWeight = 0
bestItem = 0
for i in range(len(values)):
if weights[i] >0:
if values[i]/weights[i] > maxValueWeight:
maxValueWeight = values[i]/weights[i]
bestItem = i
return bestItem
def getOptimalValue(capacity, values, weights):
totalValue = 0
tempWeight = 0
for _ in range(len(values)):
if capacity==0:
return totalValue
i = getBestItem(values, weights)
if weights[i] < capacity:
tempWeight = weights[i]
else:
tempWeight = capacity
totalValue = totalValue + tempWeight*values[i]/weights[i]
weights[i] = weights[i]-tempWeight
capacity = capacity-tempWeight
return totalValue
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 = getOptimalValue(capacity, values, weights)
print("{:.10f}".format(opt_value))
|
