8000 Add dp programs · AllAlgorithms/java@db18614 · GitHub
[go: up one dir, main page]
Skip to content

Commit db18614

Browse files
suraj-goelabranhe
suraj-goel
authored and
abranhe
committed
Add dp programs
1 parent bec71b7 commit db18614

File tree

2 files changed

+88
-0
lines changed

2 files changed

+88
-0
lines changed

‎dynamic-programming/EDIST.java

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
2+
// A Naive recursive Java program to find minimum number
3+
// operations to convert str1 to str2
4+
class EDIST
5+
{
6+
static int min(int x,int y,int z)
7+
{
8+
if (x<=y && x<=z) return x;
9+
if (y<=x && y<=z) return y;
10+
else return z;
11+
}
12+
13+
static int editDist(String str1 , String str2 , int m ,int n)
14+
{
15+
// If first string is empty, the only option is to
16+
// insert all characters of second string into first
17+
if (m == 0) return n;
18+
19+
// If second string is empty, the only option is to
20+
// remove all characters of first string
21+
if (n == 0) return m;
22+
23+
// If last characters of two strings are same, nothing
24+
// much to do. Ignore last characters and get count for
25+
// remaining strings.
26+
if (str1.charAt(m-1) == str2.charAt(n-1))
27+
return editDist(str1, str2, m-1, n-1);
28+
29+
// If last characters are not same, consider all three
30+
// operations on last character of first string, recursively
31+
// compute minimum cost for all three operations and take
32+
// minimum of three values.
33+
return 1 + min ( editDist(str1, str2, m, n-1), // Insert
34+
editDist(str1, str2, m-1, n), // Remove
35+
editDist(str1, str2, m-1, n-1) // Replace
36+
);
37+
}
38+
39+
public static void main(String args[])
40+
{
41+
String str1 = "sunday";
42+
String str2 = "saturday";
43+
44+
System.out.println( editDist( str1 , str2 , str1.length(), str2.length()) );
45+
}
46+
}

‎dynamic-programming/Knapsack.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
2+
// A Dynamic Programming based solution for 0-1 Knapsack problem
3+
class Knapsack
4+
{
5+
6+
// A utility function that returns maximum of two integers
7+
static int max(int a, int b) { return (a > b)? a : b; }
8+
9+
// Returns the maximum value that can be put in a knapsack of capacity W
10+
static int knapSack(int W, int wt[], int val[], int n)
11+
{
12+
int i, w;
13+
int K[][] = new int[n+1][W+1];
14+
15+
// Build table K[][] in bottom up manner
16+
for (i = 0; i <= n; i++)
17+
{
18+
for (w = 0; w <= W; w++)
19+
{
20+
if (i==0 || w==0)
21+
K[i][w] = 0;
22+
else if (wt[i-1] <= w)
23+
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
24+
else
25+
K[i][w] = K[i-1][w];
26+
}
27+
}
28+
29+
return K[n][W];
30+
}
31+
32+
33+
// Driver program to test above function
34+
public static void main(String args[])
35+
{
36+
int val[] = new int[]{60, 100, 120};
37+
int wt[] = new int[]{10, 20, 30};
38+
int W = 50;
39+
int n = val.length;
40+
System.out.println(knapSack(W, wt, val, n));
41+
}
42+
}

0 commit comments

Comments
 (0)
0