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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
import java.util.Arrays;
import java.util.Scanner;
import java.util.concurrent.ThreadLocalRandom;
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[sortedAscendingIndex[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) {
// int weight = 50;
// int numOfItems = 3;
//
// while (true) {
// int[] values = new int[numOfItems];
// int[] weights = new int[numOfItems];
// for (int i = 0; i < weights.length; i++) {
// values[i] = ThreadLocalRandom.current().nextInt(0, 50);
// weights[i] = ThreadLocalRandom.current().nextInt(1, 50);
// }
// int[] values1 = values.clone();
// int[] values2 = values.clone();
// int[] weights1 = weights.clone();
// int[] weights2 = weights.clone();
// double result1 = getOptimalValue(weight, values1, weights1);
// double result2 = getOptimalValueNaive(weight, values2, weights2);
//
// if (result1!=result2) {
// System.out.println(Arrays.toString(values));
// System.out.println(Arrays.toString(weights));
// System.out.println(result1);
// System.out.println(result2);
// break;
// }
// }
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();
}
public static int getBestItem(int[] values, int[] weights) {
double maxValuePerWeight = 0;
int bestItem = 0;
for (int i = 0; i < weights.length; i++) {
if (weights[i] > 0) {
if ((double) values[i] / weights[i] > maxValuePerWeight) {
maxValuePerWeight = (double) values[i] / weights[i];
bestItem = i;
}
}
}
return bestItem;
}
public static double getOptimalValueNaive(int capacity, int[] values, int[] weights) {
double totalValue = 0;
int tempWeight = 0;
for (int i = 0; i < weights.length; i++) {
if (capacity == 0)
return totalValue;
int j = getBestItem(values, weights);
if (weights[j] < capacity)
tempWeight = weights[j];
else
tempWeight = capacity;
totalValue = totalValue + tempWeight * ((double) values[j] / weights[j]);
weights[j] = weights[j] - tempWeight;
capacity = capacity - tempWeight;
}
return totalValue;
}
}
|
