add 0-1 knapsack

dpacmen · web-flow · commit 455876723ba3 · 2017-10-03T09:38:34.000+05:30
Very frequently asked DP problem
diff --git a/Dynamic Programming/Knapsack.java b/Dynamic Programming/Knapsack.java
@@ -0,0 +1,38 @@
+// A Dynamic Programming based solution for 0-1 Knapsack problem
+
+public class Knapsack
+{
+    
+	private static int knapSack(int W, int wt[], int val[], int n)
+	{
+		int i, w;
+	int rv[][] = new int[n+1][W+1];    //rv means return value
+	
+	// Build table rv[][] in bottom up manner
+	for (i = 0; i <= n; i++)
+	{
+		for (w = 0; w <= W; w++)
+		{
+			if (i==0 || w==0)
+				rv[i][w] = 0;
+			else if (wt[i-1] <= w)
+				rv[i][w] = Math.max(val[i-1] + rv[i-1][w-wt[i-1]], rv[i-1][w]);
+			else
+				rv[i][w] = rv[i-1][w];
+		}
+	}
+	
+	return rv[n][W];
+	}
+
+
+	// Driver program to test above function
+	public static void main(String args[])
+	{
+		int val[] = new int[]{50, 100, 130};
+	int wt[] = new int[]{10, 20, 40};
+	int W = 50;
+	int n = val.length;
+	System.out.println(knapSack(W, wt, val, n));
+	}
+}
