diff options
author | Haidong Ji | 2018-09-05 22:19:43 -0500 |
---|---|---|
committer | Haidong Ji | 2018-09-05 22:19:43 -0500 |
commit | bddfc348f5dbf69c004049f74939f2c837cca945 (patch) | |
tree | 8dae6c5c044ffe167cca80c465582af0d62e3641 /AlgoDesignAndTechniqueEdxJava/sources | |
parent | 2a23f32bd6db02252509d0d9fdddc0b44b10056a (diff) |
Buggy FractionalKnapsack for now. Work on a python version first.
I may need to do an exhaustive testing.
Diffstat (limited to 'AlgoDesignAndTechniqueEdxJava/sources')
-rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java | 49 |
1 files changed, 49 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java b/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java new file mode 100644 index 0000000..f16fbc7 --- /dev/null +++ b/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java @@ -0,0 +1,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(); + } + +} |