Given a rod of length N inches and an array of prices that contains prices for all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.
Input: First input line consists of N, denoting the size of array. Second line of price of ith length piece. Output: Print maximum price that can be obtained by selling the pieces.
Input: Length of rod: 8 Prices of pieces: 1 5 6 9 12 15 13 20 Output: maximum price that can be obtained: 20
Let us first understand the input format
Each element in the array represent price of length i where i is the index (considering 1-indexing).
So, for the above example:
Price of length 1: 1 (arr) Price of length 2: 5 (arr) Price of length 3: 6 (arr) Price of length 4: 9 (arr) Price of length 5: 12 (arr) Price of length 6: 15 (arr) Price of length 7: 13 (arr) Price of length 8: 20 (arr)
Now, the thing is cutting the rod recursively. Like you have to option;
- Cut of ith length and recur for remaining
- Else don't cut of that length.
The recursive function can be written as:
f(n) = maximum (f(i)+f(n-i)) where 1 ≤ i< n
In the above example, it's found that if we don't cut into pieces, if we sell the whole rod as 1 piece, then it would maximize profit to 20. All other options will lead to less amount of profit.
Also, if we make 4 pieces of length 2, would have same profit, 20.
Let's convert the above recursion in to dynamic programing.
The sub-problem can be to solve for rod of length i where 1<=i<=n and we need to store the results of this sub-problems in a array, namely DP
Here we will use the recursive relation mentioned above
To calculate DP[i],for 2≤i≤n,
if i is 1 that follows base case,no more pieces to cut down
We could have calculated through the recursive function, but needless to say that the recursion tree would have overlapping sub-problem resulting to exponential time complexity. Hence, we converted the recursion into DP and solved.