Dynamic Programming for the confused : Rod cutting problem
What is the problem ? Rod cutting problem is very much related to any real-world problem we face. You have a rod of some size and you want to cut it into parts and sell in such a way that you get the maximum revenue out of it. Now, here is the catch, prices of different size of pieces are different and it is a possibility that a cutting into smaller pieces can fetch more revenue than selling a bigger piece, so a different strategy is needed. Before that, lets state the problem more formally, You are given a rod of size n >0, it can be cut into any number of pieces k (k ≤ n). Price for each piece of size i is represented as p(i) and maximum revenue from a rod of size i is r(i) (could be split into multiple pieces). Find r(n) for the rod of size n. The size vs price table Thought process One can see that the problem distills down to the fact : where the cuts will be ? Which one provides the maximum revenue r(4)?Read full article from Dynamic Programming for the confused : Rod cutting problem
No comments:
Post a Comment