summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java69
1 files changed, 34 insertions, 35 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java b/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java
index 49ec02b..3aa823f 100644
--- a/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java
+++ b/AlgoDesignAndTechniqueEdxJava/sources/FractionalKnapsack.java
@@ -24,41 +24,41 @@ public class FractionalKnapsack {
}
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();
+// 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;
+// }
// }
-// System.out.println(getOptimalValue(capacity, values, weights));
+ 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) {
@@ -103,7 +103,6 @@ public class FractionalKnapsack {
weights[j] = weights[j] - tempWeight;
capacity = capacity - tempWeight;
}
-
return totalValue;
}
}