Commite44016c

authored

Merge pull requestTheAlgorithms#132 from dpacmen/patch-5

Rodcuting dp approach in java

2 parents3d42e00 +b67efdf commite44016cCopy full SHA for e44016c

File tree

+33

-0

lines changed

+33

-0

lines changed

Lines changed: 33 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,33 @@`
	`1`	`+/* A Dynamic Programming solution for Rod cutting problem`
	`2`	`+ Returns the best obtainable price for a rod of`
	`3`	`+length n and price[] as prices of different pieces */`
	`4`	`+`
	`5`	`+publicclassRodCutting`
	`6`	`+{`
	`7`	`+`
	`8`	`+privatestaticintcutRod(intprice[],intn)`
	`9`	`+{`
	`10`	`+intval[] =newint[n+1];`
	`11`	`+val[0] =0;`
	`12`	`+`
	`13`	`+for (inti =1;i<=n;i++)`
	`14`	`+{`
	`15`	`+intmax_val =Integer.MIN_VALUE;`
	`16`	`+for (intj =0;j <i;j++)`
	`17`	`+max_val =Math.max(max_val,price[j] +val[i-j-1]);`
	`18`	`+`
	`19`	`+val[i] =max_val;`
	`20`	`+}`
	`21`	`+`
	`22`	`+returnval[n];`
	`23`	`+}`
	`24`	`+`
	`25`	`+//main function to test`
	`26`	`+publicstaticvoidmain(Stringargs[])`
	`27`	`+{`
	`28`	`+intarr[] =newint[] {2,5,13,19,20};`
	`29`	`+intsize =arr.length;`
	`30`	`+System.out.println("Maximum Obtainable Value is " +`
	`31`	`+cutRod(arr,size));`
	`32`	`+}`
	`33`	`+}`

Comments

(0)