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 Dynamic Programming-Rod Cutting in Java
When you run the program, the output will be:
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
Post a Comment
Thank you for vising