import java.util.*;
class Item {
int weight;
int value ;
public Item(int value, int weight) {
this.value = value;
this.weight = weight;
}
}
public class Solution {
public static double fractionalKnapsackHelper(Item items[], int capacity) {
Arrays.sort(items, (o1, o2) -> {
double ratio1 = (double) o1.value / o1.weight;
double ratio2 = (double) o2.value / o2.weight;
if (ratio1 > ratio2)
return -1;
if (ratio1 < ratio2)
return 1;
return 0;
});
double profit = 0;
for (int i = 0; i < items.length; i++) {
if (items[i].weight <= capacity) {
profit += items[i].value;
capacity -= items[i].weight;
} else {
double fracProf = (double) (capacity * items[i].value) / items[i].weight;
profit += fracProf;
break;
}
}
return profit;
}
public static double fractionalKnapsack(int[] values, int[] weights, int capacity) {
// You can code here
Item[] items = new Item[values.length];
for (int i = 0; i < values.length; i++) {
items[i] = new Item(values[i], weights[i]);
}
return fractionalKnapsackHelper(items, capacity);
}
}
Editor is loading...