Freestyle | Knapsack Unbounded | Java

devstromo · devstromo · commit 8e1fd8a135cf · 2024-01-19T23:51:04.000-03:00
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/freestyle/src/main/java/com/devstromo/dp/knapsack/knapsack01/Solution.java b/freestyle/src/main/java/com/devstromo/dp/knapsack/knapsack01/Solution.java
@@ -58,6 +58,26 @@ public int[] knapsack01With1DArraySelected(int n, int m, int[] wt, int[] profits
         return selectedItems;
     }
 
+    public int knapsackUnbounded(int n, int m, int[] wt, int[] profits) {
+        int[][] dp = new int[n][m + 1];
+        for (int capacity = 0; capacity <= m; capacity++) {
+            if (wt[0] <= capacity) {
+                dp[0][capacity] = (capacity / wt[0]) * profits[0];
+            }
+        }
+        for (int item = 1; item < n; item++) {
+            for (int capacity = 1; capacity <= m; capacity++) {
+                int includeProfit = 0;
+                int excludeProfit = dp[item - 1][capacity];
+                if (wt[item] <= capacity) {
+                    includeProfit = profits[item] + dp[item][capacity - wt[item]];
+                }
+                dp[item][capacity] = Math.max(includeProfit, excludeProfit);
+            }
+        }
+        return dp[n - 1][m];
+    }
+
     private int[][] knapsack01DP(int n, int m, int[] wt, int[] profits) {
         int[][] dp = new int[n + 1][m + 1];
         int i, w;
diff --git a/freestyle/src/test/java/com/devstromo/dp/knapsack/knapsack01/SolutionUnitTest.java b/freestyle/src/test/java/com/devstromo/dp/knapsack/knapsack01/SolutionUnitTest.java
@@ -87,4 +87,14 @@ void testKnapsack01With1DArraySelectedItems2() {
         var result = solution.knapsack01With1DArraySelected(n, w, weights, profits);
         assertArrayEquals(expectedResult, result);
     }
+
+    @Test
+    void testKnapsackUnbounded() {
+        int n = 4;
+        int w = 8;
+        var weights = new int[]{1, 2, 3, 5};
+        var profits = new int[]{1, 4, 7, 10};
+        var result = solution.knapsackUnbounded(n, w, weights, profits);
+        assertEquals(18, result);
+    }
 }
