Implement the Dynamic Programming-Rod Cutting in Java

Posted By: Achchuthan Yogarajah - 7:57 PM

Share

& Comment

Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)

length | 1 2 3 4 5  6   7  8
--------------------------------------------
price  | 1 5 8 9 10 17 17 20

And if the prices are as following, then the maximum obtainable value is 24 (by cutting in eight pieces of length 1)

length | 1 2 3 4  5  6  7  8
--------------------------------------------
price  | 3 5 8 9 10 17 17 20

The naive solution for this problem is to generate all configurations of different pieces and find the highest priced configuration. This solution is exponential in term of time complexity. Let us see how this problem possesses both important properties of a Dynamic Programming (DP) Problem and can efficiently solved using Dynamic Programming.


Implement the Rod Cutting in Java



Output of this code :

Enter the value of rod of length n = 7
[Cut_rod] Rod of Lenght = 7 and solution = 18
[Memozied_Cut_rod] Rod of Lenght = 7 and solution = 18
[Bottom_Up_Cut_rod] Rod of Lenght = 7 and solution = 18
[Extended_Bottom_Up_Cut_rod] Rod of Lenght = 7 and the cuts => 1 6
BUILD SUCCESSFUL (total time: 3 seconds)

About Achchuthan Yogarajah

I’m passionate about Web Development and Programming and I go to extreme efforts to meet my passion. I’m a believer of learning the fundamentals first. I try to understand everything little bit more than the average.

1 comments :

Post a Comment

Thank you for vising Java90.blogspot.com

Copyright © 2016 Java Examples ACHCHUTHAN.ORG. Designed by Templateism .