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.

### Like this:

Like Loading...

*Related*