Problem Introduction
Given a set of items and total capacity of a knapsack,find the maximal value of fractions of items that fit into the knapsack.
Problem Description
Task.The goal of this code problem is to implement an algorithm for the fractional knapsack problem.
Input Format.The first line of the input contains the number \(n\) of items and the capacity \(W\) of a knapsack.The next \(n\) lines define the values and weights of the items. The \(i\)-th line contain integers \(v_i\) and \(w_i\)—the value and the weight of \(i\)-th item,respectively.
Constraints.\(1 \leq n \leq 10^3, 0 \leq W \leq 2 \cdot 10^6; 0 \leq v_i \leq 2 \cdot 10^6, 0 < w_i \leq 2 \cdot 10^6\) for all \(1 \leq i \leq n.\) All the numbers are integers.
Output Format.Output the maximal value of fractions of items that fit into the knapsack.The absolution value of the difference between the answer with at least four digits after the decimal point(otherwise your answer,while being computed correctly,can turn out to be wrong because of rounding issues).
Sample 1.
Input:
3 50
60 20
100 50
120 30
Output:
180.0000
Sample 2.
Input:
1 10
500 30
Output:
166.6667
Solution
# Uses python3
import sys
import numpy as np
def get_optimal_value(capacity, weights, values):
value = 0.
indices = np.argsort([-v/w for w,v in zip(weights,values)])
for idx in indices:
if capacity <= 0:
break
weight = min(capacity, weights[idx])
capacity -= weight
value += weight * (values[idx] / weights[idx])
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))