Last Updated: 24 Oct, 2020
Rod cutting problem
Moderate
Asked in companies
Given a rod of length ‘N’ units. The rod can be cut into different sizes and each size has a cost associated with it. Determine the maximum cost obtained by cutting the rod and selling its pieces.
Note:
1. The sizes will range from 1 to ‘N’ and will be integers.
2. The sum of the pieces cut should be equal to ‘N’.
3. Consider 1-based indexing.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next 2 * T lines represent the ‘T’ test cases.
The first line of each test case contains an integer ‘N’ denoting the length of the rod.
The second line of each test case contains a vector ’A’, of size ‘N’ representing the cost of different lengths, where each index of the array is the sub-length and the element at that index is the cost for that sub-length.
Note:
Since 1-based indexing is considered, the 0th index of the vector will represent sub-length 1 of the rod. Hence the (N - 1)th index would represent the cost for the length ‘N’.
Output Format
For each test case, print a single line that contains a single integer which is the maximum cost obtained by selling the pieces.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 100
1 <= A[i] <= 100
Where ‘T’ is the total number of test cases, ‘N’ denotes the length of the rod, and A[i] is the cost of sub-length.
Time limit: 1 sec.
Approaches
- This is a recursive approach.
- Initialize a variable ‘MAXCOST’ to INT_MIN;
- In each recursive function call, run a loop where ‘I’ ranges from 0 to ‘N - 1’, and partition the rod of length ‘N’ into two parts, ‘I’ and ‘N - I’.
- Example For a rod of length 5, for 'I' = 2, the two partitions will be 2 and 3.
1. Take ‘I’ as the first cut in the rod and keep it constant. Now, a rod of ‘N - I - 1’ remains. Pass the remaining rod of size ‘N - I - 1’ to the recursion.
2. Step 1 continues until it hits the base condition, which is when the length of the rod becomes zero.
3. When the recursion hits the base condition, the cost of a particular configuration is obtained.
4. Compare it with the ‘MAXCOST’ variable and store the maximum of the cost in variable ‘MAXCOST’. - For every ‘I’ as an initial sub-length, different configurations are obtained and compared to the ‘MAXCOST’ variable.
- Lastly, ‘MAXCOST’ contains the final answer.
The approach is similar to the Unbounded knapsack problem. The idea is to select a sub-length of rod out of all possible sub-lengths, as one option and ignore this sub-length, as another option.
In this way, we will get all possible configurations and we calculate the ‘MAXCOST’ for all the possible configurations and return the maximum of them all.
- Take a two-state dp, 'COST'['N']['MAXLEN'], where 'N' denotes the sub-length of the rod to be processed and max_length denotes the rod left uncut.
Calculate all possible configurations using recursion.
1. If the length of the sub-length of rod considered is less than or equal to the max_length, that is, the rod left uncut, then for a particular sub-length,'X',
a. Either include it and reduce the max-length by 'X' and recur.
b. Or exclude it and keep the max-length unchanged and recur.
2. Else, recur with reducing the value of 'N' but keeping max_length unchanged.
Keep storing the maximum 'COST' at every step in the dp array, 'COST'[ ][ ] so that it need not be re-calculated further.
The value of the greater lengths is calculated by selecting the maximum value from all the possible configurations of shorter lengths.
Lastly, 'COST'['N']['MAXLEN'] stores the maximum 'COST' obtained for a rod of length 'N'.
Following is a recursion tree for a rod of length 3.
We can observe that the problem has optimal substructure and overlapping subproblems and hence can be solved using dynamic programming. The idea is to store the results of subproblems so that we do not have to re-compute them when they are needed.
Below is a bottom-up approach, in which smaller subproblems are stored first which are used to solve the larger sub-problems. The below approach computes ‘COST[i]’, which stores maximum profit achieved from the rod of length i for each 1 <= i <= 'N'. It uses the 'COST' of smaller values of 'I' already computed.
- Declare an array, ‘COST’ of size ‘'N'+1’ and initialize 'COST'[0] = 0. We use this 1 D array to store the previous COST and with every iteration, we update the COST.
- Run a loop where 1<= 'I' <= 'N'. Consider ‘'I'’ as the length of the rod.
- Divide the rod of length 'I' into two rods of length 'J' and 'I' - 'J' - 1 using a nested loop in which 0<=j<'I'. Find the COST of this division using A['J'] + COST[i - j -1] and compare it with the already existing value in the array COST[].
- Store the maximum value at every index 'X', which represents the maximum value obtained for partitioning a rod of length ‘X’.
- For a greater length, all the possible combinations are formed with all the pre-calculated shorter lengths, and the maximum of them is stored in a COST array with every iteration.
- Lastly, COST[N] stores the maximum COST obtained for a rod of length 'N'.