AllAlgorithms · abranhe · Oct 2, 2018 · Oct 2, 2018
diff --git a/dynamic-programming/EDIST.java b/dynamic-programming/EDIST.java
@@ -0,0 +1,46 @@
+
+// A Naive recursive Java program to find minimum number 
+// operations to convert str1 to str2 
+class EDIST 
+{ 
+    static int min(int x,int y,int z) 
+    { 
+        if (x<=y && x<=z) return x; 
+        if (y<=x && y<=z) return y; 
+        else return z; 
+    } 
+
+    static int editDist(String str1 , String str2 , int m ,int n) 
+    { 
+        // If first string is empty, the only option is to 
+    // insert all characters of second string into first 
+    if (m == 0) return n; 
+
+    // If second string is empty, the only option is to 
+    // remove all characters of first string 
+    if (n == 0) return m; 
+
+    // If last characters of two strings are same, nothing 
+    // much to do. Ignore last characters and get count for 
+    // remaining strings. 
+    if (str1.charAt(m-1) == str2.charAt(n-1)) 
+        return editDist(str1, str2, m-1, n-1); 
+
+    // If last characters are not same, consider all three 
+    // operations on last character of first string, recursively 
+    // compute minimum cost for all three operations and take 
+    // minimum of three values. 
+    return 1 + min ( editDist(str1,  str2, m, n-1),    // Insert 
+                     editDist(str1,  str2, m-1, n),   // Remove 
+                     editDist(str1,  str2, m-1, n-1) // Replace                      
+                   ); 
+    } 
+
+    public static void main(String args[]) 
+    { 
+        String str1 = "sunday"; 
+        String str2 = "saturday"; 
+
+        System.out.println( editDist( str1 , str2 , str1.length(), str2.length()) ); 
+    } 
+}
diff --git a/dynamic-programming/Knapsack.java b/dynamic-programming/Knapsack.java
@@ -0,0 +1,42 @@
+
+// A Dynamic Programming based solution for 0-1 Knapsack problem 
+class Knapsack 
+{ 
+
+    // A utility function that returns maximum of two integers 
+    static int max(int a, int b) { return (a > b)? a : b; } 
+
+   // Returns the maximum value that can be put in a knapsack of capacity W 
+    static int knapSack(int W, int wt[], int val[], int n) 
+    { 
+         int i, w; 
+     int K[][] = new int[n+1][W+1]; 
+
+     // Build table K[][] in bottom up manner 
+     for (i = 0; i <= n; i++) 
+     { 
+         for (w = 0; w <= W; w++) 
+         { 
+             if (i==0 || w==0) 
+                  K[i][w] = 0; 
+             else if (wt[i-1] <= w) 
+                   K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]); 
+             else
+                   K[i][w] = K[i-1][w]; 
+         } 
+      } 
+
+      return K[n][W]; 
+    } 
+
+
+    // Driver program to test above function 
+    public static void main(String args[]) 
+    { 
+        int val[] = new int[]{60, 100, 120}; 
+    int wt[] = new int[]{10, 20, 30}; 
+    int  W = 50; 
+    int n = val.length; 
+    System.out.println(knapSack(W, wt, val, n)); 
+    } 
+}