blob: f16fbc779b43853613ecf1e6a8e281dda0dbd9e0 (
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
38
39
40
41
42
43
44
45
46
47
48
49
|
import java.util.Scanner;
import java.util.stream.IntStream;
public class FractionalKnapsack {
public static double getOptimalValue(int capacity, int[] values, int[] weights) {
double totalValue = 0;
int tempWeight = 0;
int[] sortedAscendingIndex = getSortedIndexArray(values, weights);
for (int i = sortedAscendingIndex.length - 1; i >= 0; i--) {
if (capacity == 0)
return totalValue;
if (weights[i] < capacity)
tempWeight = weights[sortedAscendingIndex[i]];
else
tempWeight = capacity;
totalValue = totalValue
+ tempWeight * ((double) values[sortedAscendingIndex[i]] / weights[sortedAscendingIndex[i]]);
capacity = capacity - tempWeight;
}
return totalValue;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int capacity = scanner.nextInt();
int[] values = new int[n];
int[] weights = new int[n];
for (int i = 0; i < n; i++) {
values[i] = scanner.nextInt();
weights[i] = scanner.nextInt();
}
System.out.println(getOptimalValue(capacity, values, weights));
}
public static int[] getSortedIndexArray(int[] values, int[] weights) {
// https://stackoverflow.com/questions/4859261/get-the-indices-of-an-array-after-sorting
double[] valueWeightRatio = new double[values.length];
for (int i = 0; i < values.length; i++) {
valueWeightRatio[i] = (double) values[i] / weights[i];
}
return IntStream.range(0, values.length).boxed()
.sorted((i, j) -> Double.compare(valueWeightRatio[i], valueWeightRatio[j])).mapToInt(ele -> ele)
.toArray();
}
}
|
