Rod Cutting Problem using Top-down Dynamic Programming .
What is Dynamic Programming ?
A Dynamic Programming is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states. A sub-solution of the problem is constructed from previously found ones. DP solutions have a polynomial complexity which assures a much faster running time than other techniques like backtracking, brute-force etc.
Methods to solve dynamic programming :
Top down :
In this approach, we try to solve the bigger problem by recursively finding the solution to smaller sub-problems. Whenever we solve a sub-problem, we cache its result so that we don’t end up solving it repeatedly if it’s called multiple times. Instead, we can just return the saved result. This technique of storing the results of already solved subproblems is called Memoization.
Bottom Up:
Tabulation is the opposite of the top-down approach and avoids recursion. In this approach, we solve the problem “bottom-up” (i.e. by solving all the related sub-problems first). This is typically done by filling up an n-dimensional table. Based on the results in the table, the solution to the top/original problem is then computed.
Tabulation is the opposite of Memoization, as in Memoization we solve the problem and maintain a map of already solved sub-problems. In other words, in memoization, we do it top-down in the sense that we solve the top problem first.
Characteristics of Dynamic Programming :
Overlapping Subproblems:
Subproblems are smaller versions of the original problem. Any problem has overlapping sub-problems if finding its solution involves solving the same subproblem multiple times. Take a look at the following figure; to find the F4, we need to break it down into the following sub-problems.
F4 is divided in to F3 ,F2,F1andF0 and again F3 is further divided in to F2,F1 and F0.So, here F2 should be computed twice hence it is an over lapping sub problem.F1 and F0 are also over lapping subproblems in the given figure.
Optimal Substructure :
Any problem has optimal substructure property if its overall optimal solution can be constructed from the optimal solutions of its subproblems.There may be several paths that can be followed in order to get the final solution .Among all those several paths we need to find and select only the path which is more efficient Just as like if there are several routes to a destination point from a single common start point then we should have to consider the only efficient route which is efficient(i.e less distance ).
The Rod-Cutting Problem:
In this problem a rod of length n is taken, and an array that contains the prices of all the pieces smaller than n, determine the maximum profit you could obtain from cutting up the rod and selling its pieces.
A rod of length 5 is taken and on the right hand side we can see the different ways of cutting the rod .
Recursive Approach:
This problem can be solved by using recursive approach whose pseudo code can be as follows
int cutRod(int price[], int n, int i) {
if(n<1)
return 0;
for(int i=0;i<=n;i++){
int m= max(price[i-1] + cutRod(price,n-(i+1),i),m);
}
return m;
}
Overlapping subproblems and optimal substructure condition in the rod cutting problem:
Overlapping Subproblems:
We can clearly observe from the above figure that identical subproblems are coloured in identical colours like rod of length 4 is our assumed problem is divided in to 3,2,1,and again each sub problem is further divided in to smaller sub problems like 3 in to 2,1 and 2 in to 1.
So, Here subproblems indicated as 2 and 1 are repeated more than once.
Hence we can see the overlapping sub problems.
Optimal Substructure :
From the above figure we can see the solutions can be obtained in many different ways which can be indicated as arrow marks pointing from number 4 to zero. From all the different possible solutions we have to select the the maximum possible solution.
Hence we can apply the dynamic programing to solve the Rod cutting problem.
Rod cutting problem using Top Down Approach with memoisation Dp :
The Top down Approach :
From the above figure,we can see the number of possible ways of dividing a single rod of given length in to smaller rods of variable lengths in various ways .we need to compute the maximum cost that can be obtained from the above mentioned all possible cases.
The difference between both recursive and top down approach is that in the recursive approach
We need to compute the solution to the sub-problems multiple number of times which requires more time results in the more time complexity in the algorithm.
But in top down memoised approach we can eliminate this disadvantage by using a special type of array called memoised array which can be denoted as memo[ ],in which we have to store the precomputed solution of the smaller sub problems in the memo[ ] array.
By storing all the precomputed results of the smaller sub problems in the memo [ ] array ,we can use those results in consecutive iterations where again the same sub problem is repeated instead of computing the single subproblem multiple times we can simply take the result of that sub problem from the memo[ ] array.
Implementation of the rod cutting problem using Top-down approach with memoization Dp in cpp:
int RC(int p[ ],int n,int memo[ ]){ //Rod Cutting Function
if(n<=0) {
return 0;
}
if(memo[p]>0){
return memo[p];
}
else {
int m = INT_MIN;
for (int i = 1; i <= p; i++) {
m = max(m, a[i] + RC(a, p — i,memo));
}
memo[p]=m;
return memo[p];
}
}
In the above shown recursive approach which is an example of a rod of length 4 after the computation of the left most sub problem our memoised array is filled with all the results of the smaller subproblems indexed as 3,2 and 1 which can be further used to omit the recomputation
Of the subproblems like 2 and 1 which are highlighted in the given diagram.
