Recursive Memoization Knapsack in Java

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 following code is the main method for calling the two Knapsack methods:

public static void main(String[] args){
	int[][] dp1 = new int[3][4];

	for(int i = 0; i < dp1.length; i++){
		for(int j = 0; j < dp1[0].length; j++){
			dp1[i][j] = -1;
		}
	}

	System.out.println(knapsack01(2, 3, new int[]{1, 2, 3}, new int[]{1, 2, 4}, dp1));

	int[] dp2 = new int[4];

	Arrays.fill(dp2, -1);

	System.out.println(knapsackUnbounded(3, new int[]{1, 2, 3}, new int[]{3, 2, 1}, dp2));
}

 

Full code available here: https://github.com/Daniel-Liu-c0deb0t/General-Algorithms/blob/master/Knapsack.java

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!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s