Kite cutting problem using Dynamic programming program

Cloth cutting or kite cutting problem is well known problem of DP (Dynamic programming) used in real life.

Here we have sheet of 9x10 and we want to divide it in such a way that we get maximum value.

 Price of subsheets are     2x3=50 and 3x5=100.

Code

public class kite_cutting 

{

public static void main(String strd[]) 

{

int M=9,N=10; //Given SIze of sheet= 9x10

M++; //Make space for 0

N++;

int sheet[][]=new int[M][N];

sheet[2][3]=50; //Already given the value 2x3=50

sheet[3][2]=50;

sheet[3][5]=100;//Already given the value 3x5=50

sheet[5][3]=100;

//initialize first row and column to 0.

for(int i=0;i<M;i++)

sheet[i][0]=0; 

for(int i=0;i<N;i++)

sheet[0][i]=0;

int temp;

//Start DP

for (int i = 0; i < M; i++) 

{

for (int j = 0; j < N; j++) 

{

temp=0;

//Cut the sheet horizontally upto i/2

for (int k = 0; k <= i/2 ; k++) 

{

if(temp<(sheet[k][j]+sheet[i-k][j]))

{

temp=(sheet[k][j]+sheet[i-k][j]);

}

}

//cut the sheet vertically upto j/2

for (int k = 0; k <= j/2 ; k++) 

{

if(temp<(sheet[i][k]+sheet[i][j-k]))

{

temp=(sheet[i][k]+sheet[i][j-k]);

}

}

//store max temp into table

sheet[i][j]=temp;

}

}

//print Table

for (int i = 0; i < M; i++) 

{

System.out.print(i +"||\t");

for (int j = 0; j < N; j++) 

{

System.out.print(sheet[i][j]+"\t");

}

System.out.println();

}

for (int j = 0; j < N; j++)

{

System.out.print("-------------");

}

System.out.print("\n\t");

for (int j = 0; j < N; j++)

{

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

}

System.out.println("\n Maximum values we get from sheet is "+sheet[M-1][N-1]);

}

}

Download Source Code in Java
click on above link to get source code