The Knapsack problem is a Dynamic Programming problem. We have to maximize the total value of the items, while making sure the total weight of the items is lower than a specific value. There are two variations to this problem:

### 0/1 Knapsack

In this variation, we can only pick at most one of each item. We can either pick (1) or not pick (0), hence the name. A regular recursive implementation would have an O(2^n) running time, as we have two choices for each item. However, with memoization, we can save the states (current item we are on and remaining weight available defines the state) that give the maximum value, reducing the running time of the program.

A simple implementation is given:

public static int knapsack01(int i, int w, int[] weights, int[] values, int[][] dp){ if(i < 0) return 0; if(dp[i][w] != -1) return dp[i][w]; if(w < weights[i]) dp[i][w] = knapsack01(i - 1, w, weights, values, dp); else dp[i][w] = Math.max(knapsack01(i - 1, w, weights, values, dp), values[i] + knapsack01(i - 1, w - weights[i], weights, values, dp)); return dp[i][w]; }

### Unbounded Knapsack

What if you can take multiple of one item? Every single recursive call it would have to call itself again with all of the different items. With memoization, we can save the states (remaining weight available defines the state) and reduce the run time of the program.

A simple implementation:

public static int knapsackUnbounded(int w, int[] weights, int[] values, int[] dp){ if(dp[w] != -1) return dp[w]; int max = 0; for(int i = 0; i < weights.length; i++){ if(weights[i] <= w) max = Math.max(max, values[i] + knapsackUnbounded(w - weights[i], weights, values, dp)); } dp[w] = max; return dp[w]; }

The full code is available here, and it includes a main method that tests the two implementations above.

Dynamic Programming problems can be tricky at times, but when you think of them as regular recursion + memoization, the program becomes much easier to write. Thanks for reading!