summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-26 18:02:55 -0600
committerHaidong Ji2018-12-26 18:02:55 -0600
commite09a3494e3f3b957b10402d9252a0bddec4cc908 (patch)
tree4c8de2d4beafc9b452a30b5e6900187c5850a031
parente3e21cb0f76d24bc365898efe5a45b59226da00e (diff)
Knapsack maximize gold done!
It was a bit tricky translating algo in course slide to code, especially regarding array indexing. I left a bit and walked the dogs. After I came back, my mind was clearer than before. Debugging after that solved the problem!
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/Knapsack.java41
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/KnapsackTest.java14
2 files changed, 55 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxJava/sources/Knapsack.java b/AlgoDesignAndTechniqueEdxJava/sources/Knapsack.java
new file mode 100644
index 0000000..97e89aa
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/sources/Knapsack.java
@@ -0,0 +1,41 @@
+import java.util.Scanner;
+
+public class Knapsack {
+
+ public static void main(String[] args) {
+ Scanner scanner = new Scanner(System.in);
+ int W, n;
+ W = scanner.nextInt();
+ n = scanner.nextInt();
+ int[] w = new int[n];
+ for (int i = 0; i < n; i++) {
+ w[i] = scanner.nextInt();
+ }
+ System.out.println(optimalWeight(W, w));
+ }
+
+ public static int optimalWeight(int W, int[] w2) {
+ int j = w2.length;
+ int[][] value = new int[W + 1][j + 1];
+
+ for (int i = 0; i < j + 1; i++) {
+ for (int w = 0; w < W + 1; w++) {
+ if (i == 0 || w == 0) {
+ value[w][i] = 0;
+ continue;
+ }
+ value[w][i] = value[w][i - 1];
+ if (w2[i - 1] <= w) {
+ int val = value[w - w2[i - 1]][i - 1] + w2[i - 1];
+ if (value[w][i] < val) {
+ value[w][i] = val;
+ }
+ }
+ }
+
+ }
+
+ return value[W][j];
+ }
+
+}
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/KnapsackTest.java b/AlgoDesignAndTechniqueEdxJava/tests/KnapsackTest.java
new file mode 100644
index 0000000..86624c7
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxJava/tests/KnapsackTest.java
@@ -0,0 +1,14 @@
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class KnapsackTest {
+
+ @Test
+ void test() {
+ int[] w = { 1, 4, 8 };
+ int W = 10;
+ assertEquals(9, Knapsack.optimalWeight(W, w));
+ }
+
+}