-
Notifications
You must be signed in to change notification settings - Fork 0
/
P46.java
38 lines (36 loc) · 915 Bytes
/
P46.java
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
import java.util.*;
import java.io.*;
/****************************************************************
*
* Following is the class structure of the Pair class:
*
* class Pair
* {
* int weight;
* int value;
* Pair(int weight, int value)
* {
* this.weight = weight;
* this.value = value;
* }
*
* }
*
*****************************************************************/
public class P46 {
public static double maximumValue(Pair[] item, int n, int w) {
// Greedy
Arrays.sort(item, (p, q) -> p.weight * q.value - q.weight * p.value);
double res = 0.0;
for (int i = 0; i < n; i++) {
if (item[i].weight <= w) {
res += item[i].value;
w -= item[i].weight;
} else {
res += (((double) item[i].value * w / item[i].weight));
break;
}
}
return res;
}
}