matrix chain multiplication by dynamic programming approach (java implementation)

Source Code

Source Code

        
    
 package dynamic;

public class MatrixChainMultiplication {

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  System.out.println("Program is running");
int[] q={2,5,3,5,2,3,5};
int [][] m=matrixChain(p);

System.out.println("Total cost of multiplication matrix:");
for(int i=1;i
    
    

Java implementation of Floyd -Warshall algorithm for all pair shortest path problem by dynamic programming approach

Source Code:

package dynamic;

public class Floyd {

public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Program is running...");


int [][]w={
{0,4,11},
{6,0,2},
{3,Integer.MAX_VALUE,0}
};



int [][] d=floydShortestPath(w,3);

for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
System.out.print(d[i][j]+"   ");
}
System.out.println();
}


}

public static int [][] floydShortestPath(int [][] w,int n){

int [][] d=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){

d[i][j]=w[i][j];

}
}

for(int k=0;k<n;k++){

for(int i=0;i<n;i++){
for(int j=0;j<n;j++){

if(d[i][j]>d[i][k]+d[k][j])
d[i][j]=d[i][k]+d[k][j];
}
}
}


return d;
}



}

java implementation of 0-1 knapsack problem by dynamic programming approach

Source code:

package dynamic;

public class Knapsack {

public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Program is running");

//input to the function 
int W=5;//knapsack capacity
int n=4;
int [] v={3,4,5,6};
int [] w={2,3,4,5};
 
int [][] c=dynamicKnapsack(W,n,v,w);
for(int i=0;i<=n;i++){
for(int j=0;j<=W;j++){
System.out.print(c[i][j]+"  ");
}
System.out.println();
}
 
solution(c,w,W,n);

}

public static int[][] dynamicKnapsack(int W, int n,int [] v,int w[]){

int [][] c=new int [n+1][W+1];//solution matrix



for(int i=0;i<=n;i++)
c[i][0]=0;

for(int weight=1;weight<=W;weight++)
c[0][weight]=0;

for(int i=1;i<=n;i++){
for(int weight =1;weight<=W;weight++){


if(w[i-1]<=weight){
if(c[i-1][weight] <c[i-1][weight -w[i-1]]+v[i-1])
{
c[i][weight]=c[i-1][weight -w[i-1]]+v[i-1];
}
else 
c[i][weight]=c[i-1][weight];
}
else
c[i][weight]=c[i-1][weight];


}

}


return c;

}
public static void solution (int [][]c,int [] weight,int W,int n){
System.out.println("Maximum Profit ="+c[n][W]);
for(int i=n;i>0;){
for(int w=W;w>0;){
if(c[i][w]!=c[i-1][w]){
System.out.println("Add item "+ (i-1));
i--;
w=w-weight[i];

}
else i--;w--;
}
}


}



}

java implementation of Longest chain subsequence problem by dynamic programming approach

Source code:

package dynamic;

public class LCS {

public static void main(String[] args) {

// TODO Auto-generated method stub

System.out.println("Program is running ...");

Solution s=longestSequence("abbaab","aabaabb");

for (int i=0;i<=s.m1;i++){

for (int j=0;j<=s.n1;j++){

System.out.print(s.c[i][j]+"  ");

}

System.out.println();

}

System.out.println("The solution matrix b is");

String str;

for (int i=0;i<=s.m1;i++){

for (int j=0;j<=s.n1;j++){

if(s.b[i][j]=='a'){

System.out.print("up"+"\t");

}

if(s.b[i][j]=='u'){

System.out.print("upleft "+"\t");

}

if(s.b[i][j]=='l'){

System.out.print("left"+"\t");

}

}

System.out.println();

}

}

public static Solution longestSequence (String x,String y){

int m=x.length();

int n=y.length();

/*

* solution matrix b

* in whic u=upleft

* a=up

* and l=left

*/

 Solution s=new Solution(m,n);

 

 

 

for(int i=1;i<=m;i++) s.c[i][0]=0;

for(int j=0;j<=n;j++) s.c[0][j]=0;

for (int i=1;i<=m;i++){

for (int j=1;j<=n;j++){

if(x.charAt(i-1)==y.charAt(j-1)){

s.c[i][j]=s.c[i-1][j-1]+1;

s.b[i][j]='u';

}

else if(s.c[i-1][j]>s.c[i][j-1]){

s.c[i][j]=s.c[i-1][j];

s.b[i][j]='a';

}

else 

{

s.c[i][j]=s.c[i][j-1];

s.b[i][j]='l';

}

}

}

return s;

}

}

package dynamic;

public class Solution {

public  int [][]c;

public  char [][]b;

public int m1,n1;

public Solution(int m1,int n1){

this.c=new int [m1+1][n1+1];

this.b=new char[m1+1][n1+1];

this.m1=m1;

this.n1=n1;

}

public Solution(){

}}