KnapSack problem

The knapsack problem is a very classic problem that can be solved using dynamic programming. Here is a description of that problem.

A thief broke into a store with a bag that can hold as much as goods of total weight of W. There are n goods in the store and each have a wait of wt and value v, stored in two arrays. The question is which out of the n goods the thief should pick that can fit in his knapsack and with the highest value.

At the first glace, the recursive solution seems obvious, we either pick item i or we don’t. So we write the code

public static int knapSack (int W, int n, int [] wt, int[] v) {
		if (n == 0)
			return wt[0] <= W ? v[0] : 0; // if can fit
		if (wt[n] > W) {
			return knapSack(W, n-1, wt, v);
		}
		return Math.max(knapSack(W-wt[n], n-1, wt, v) + v[n], // with the nth element in the bag 
						knapSack(W, n-1, wt, v) //without the nth element
				);
}

The runtime of this algorithm is n^2

So let us proceed to the dynamic programming, calculate for each element n and each bag size W

	public static int knapSack (int W, int n, int [] wt, int[] v) {
		int [][] dp = new int [n+1][W+1];
		for (int i = 0; i < n+1; i++) {
			for (int j = 0; j < W+1; j++) {
				if (i == 0)
					dp[i][j] = wt[i] <= j? v[i] : 0;
				else {
					if (wt[i] <= j) {
						dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - wt[i]] + v[i]);
					}
					else
						dp[i][j] = dp[i-1][j];
				}
			}
		}
		return dp[n][W];
	}

The running time of the algorithm is O(n*W), but it is still an NP-hard problem because W is independent with the input size n and could be potentially a huge number.

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