This post is completed by 2 users
|Add to List|
Dynamic Programming - Rod Cutting Problem
Objective: Given a rod of length n inches and a table of prices pi, i=1,2,…,n, write an algorithm to find the maximum revenue rn obtainable by cutting up the rod and selling the pieces.
Given: Rod lengths are integers and For i=1,2,…,n we know the price pi of a rod of length i inches
for rod of length: 4 Ways to sell : • selling length : 4 ( no cuts) , Price: 9 • selling length : 1,1,1,1 ( 3 cuts) , Price: 4 • selling length : 1,1,2 ( 2 cuts) , Price: 7 • selling length : 2,2 ( 1 cut) , Price: 10 • selling length : 3, 1 ( 1 cut) , Price: 9
Best Price for the rod of length 4: 10
Naive Approach: Recursion
- There can be n-1 cuts can be made in the rod of length n, so there are 2n-1 ways to cut the rod.
- So for every length, we have 2 options either we cut it or not. we will consider both options and choose the optimal out of it.
Time Complexity: O(2^n-1)
But this time complexity is very high since we are solving many subproblems repeatedly.
Dynamic Programming: Bottom-Up
Instead of solving the sub-problems repeatedly we can store the results of it in an array and use it further rather than solving them again.
See the Code for a better explanation:
Result: Max profit for length is 5:11
- Maximum difference between two elements where larger element appears after the smaller element Medium