Title: Dynamic Programming | 0-1 Knapsack Problem Source: www.geeksforgeeks.org
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).
A simple solution is to consider all subsets of items and calculate the total weight and value of all subsets. Consider the only subsets whose total weight is smaller than W. From all such subsets, pick the maximum value subset.
1) Optimal Substructure:
To consider all subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset, (2) not included in the optimal set.
Therefore, the maximum value that can be obtained from n items is max of following two values.
1) Maximum value obtained by n-1 items and W weight (excluding nth item).
2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).
If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
/* http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/ */ class KnapsackDP { // Recursive public int solve(int[] value, int[] weight, int w) { return helper(value, weight, w, 0); } public int helper(int[] value, int[] weight, int w, int i) { if(i>=value.length) return 0; if(weight[i] > w) return helper(value, weight, w, i+1); else return Math.max(value[i]+helper(value, weight, w-weight[i], i+1), helper(value, weight, w, i+1)); } //DP public int solveDP(int[] value, int[] weight, int w) { int[][] dp = new int[value.length+1][w+1]; for(int i=0; i<=value.length; i++) { for(int j=0; j<=w; j++) { if(i==0 || j==0) dp[i][j] = 0; else { if(weight[i-1] <= j) dp[i][j] = Math.max(value[i-1] + dp[i-1][j-weight[i-1]], dp[i-1][j]); else dp[i][j] = dp[i-1][j]; } } } return dp[value.length][w]; } public static void main(String args[]) { int value[] = {60, 100, 120}; int weight[] = {10, 20, 30}; int w = 50; KnapsackDP k = new KnapsackDP(); System.out.println(k.solveDP(value, weight, w)); } } |
Great solution.
But you can further reduce the space complexity to O(n).