Introduction
Suppose a company sells different lengths of steel rods they have rod prices based on length of rod. Suppose they get 10m rod as raw material and they cut it into pieces and prices of every piece are listed below:
Length(m) |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Price($) |
2 |
6 |
5 |
7 |
12 |
13 |
16 |
15 |
20 |
21 |
Now company wants maximum profit by cutting 10m rod in different chunks, so how to get maximum profit in $ and what sizes we have to cut and how many? We will solve it in implementation section.
Implementation
We will solve this problem using dynamic programming approach. We know we can cut this rod in 2n-1 ways. Yes we can use brute force and calculate all possible combinations but we know in brute force we have to solve so many sub-problems which will get repeated. For an instance suppose we have rod with only 3m length to cut, so possible combinations are:
1. {1,1,1}
2. {1,2}
3. {2,1}
4. {3}
If we see cutting rod in (1m, 2m) parts we have to calculate sum of 1m price and 2m price, in point 3 we have to calculate sum of 2m price and 1m price which we have already calculated in step 2 so we no need to calculate and directly take solution from calculation of 2nd scenario.
Memoization: We use memoization in dynamic programming where we divide problem in sub-problems, solve them and store sub-problem’s solution somewhere, if these gets repeated next time we no need to calculate and we can directly get stored results. This is called memoization, it helps to decrease running time.
Now first we will solve this problem with brute force and for that we will create a class RodCuttingManager below I'm just showing you structure of class what and all methods we are going to implement different functionalities:
public class RodCuttingManager {
int _rodSize;
int[] _sellingPrize;
public RodCuttingManager(int rodSize, int[] sellingPrize)
{
_rodSize = rodSize;
_sellingPrize = sellingPrize;
}
public int PrintMaxProfitBruteForce(){...}
public int PrintMaxProfitDynamicProgramming(){...}
public int PrintDynamicProgrammingButtomUp(){...}
public object PrintDynamicProgrammingButtomUpFullSolution(){...}
private int CutRod(int size, int[] prize){...}
private int CutRodMemoized(int size, int[] prize, int[] results){...}
private int ButtomUpCutRod(int size, int[] prize){...}
private object ButtomUpCutRodExtended(int size, int[] prize){...}
private string RodCutSolution(int size, int[] subProblems){...}
}
Above using constructor we are setting rod size and prices per piece, price[i] will describe price of length "i" and we will be having 4 public and 5 private methods which definitions we will see, first we explore PrintMaxProfitBruteForce method, which uses brute force:
public int PrintMaxProfitBruteForce() { return CutRod(_rodSize, _sellingPrize); } /// <summary> /// Simply follows brute force and calculate every possible combination /// </summary> /// <param name="size">size of rod</param> /// <param name="prize">prices list</param> /// <returns></returns> private int CutRod(int size, int[] prize) { if (size == 0) return 0; int maxProfit = Int32.MinValue; for (int i = 1; i <= size; i++) { maxProfit = Math.Max(maxProfit, prize[i] + CutRod(size - i, prize)); } return maxProfit; }
PrintMaxProfitBruteForce calls one private method CutRod which accepts rode size and respective prices of particular rod lengths, CutRod actually does the job and returns the maxProfit, but it is not optimized and we have to calculate so many sub-problems repeatedly. In our next approach will use memoization so we no need to calculate same problem more than one time, for that we need one extra array(need to increase space complexity to reduce time complexity), below we are having implementation of other private method CutRodMemoized and calling it from method PrintMaxProfitDynamicProgramming :
public int PrintMaxProfitDynamicProgramming() { int[] results = new int[_rodSize + 1]; for (int i = 1; i < results.Length; i++) results[i] = Int32.MinValue; return CutRodMemoized(_rodSize, _sellingPrize, results); } /// <summary> /// Uses memoization of dynamic programming /// </summary> /// <param name="size">size of rod</param> /// <param name="prize">prices list</param> /// <param name="results">for memoization</param> /// <returns></returns> private int CutRodMemoized(int size, int[] prize, int[] results) { if (size == 0) return 0; if (results[size] >= 0) return results[size]; //optimization int maxProfit = int.MinValue; for (int i = 1; i <= size; i++) { maxProfit = Math.Max(maxProfit, prize[i] + CutRodMemoized(size - i, prize, results)); } results[size] = maxProfit; //memoization return maxProfit; }
Above we can see extra array results is required to store the sub-problem’s solution and if we find solution we will return same without calculating again. You can see two comments optimization and memoization are actual extra code we added to achieve that.
But above solution is recursive and it is actually top-down approach because we are giving full size then dividing it in sub-problems, we can do it without recursion and in bottom-up fashion, for that we need only one method which takes size and price:
public int PrintDynamicProgrammingButtomUp() { return ButtomUpCutRod(_rodSize, _sellingPrize); } /// <summary> /// ButtomUp Approach with dynamic programming /// </summary> /// <param name="size">size of rod</param> /// <param name="prize">prices list</param> /// <returns></returns> private int ButtomUpCutRod(int size, int[] prize) { int[] results = new int[size + 1]; for (int i = 1; i <= size; i++) { int maxProfit = Int32.MinValue; for (int j = 1; j <= i; j++) { maxProfit = Math.Max(maxProfit, results[i - j] + prize[j]); } results[i] = maxProfit; } return results[size]; }
But none of above solutions provides how many pieces of what size has to be cut, they only provide what a maximum profit, to achieve that we have to modify our ButtomCutRod method like:
/// <summary> /// Full solution, maximum profit with sizes of rod which will give max profit /// </summary> /// <param name="size"></param> /// <param name="prize"></param> /// <returns></returns> private object ButtomUpCutRodExtended(int size, int[] prize) { int[] results = new int[size + 1]; int[] subProblems = new int[size + 1]; for (int i = 1; i <= size; i++) { int maxProfit = Int32.MinValue; for (int j = 1; j <= i; j++) { if (results[i - j] + prize[j] > maxProfit) { maxProfit = results[i - j] + prize[j]; subProblems[i] = j; } } results[i] = maxProfit; } return new { MaxProfit = results[size], Solution = RodCutSolution(size, subProblems) }; } /// <summary> /// Generates cutting sizes for maximum profit /// </summary> /// <param name="size">size of rod</param> /// <param name="subProblems">Subproblems which have optimum solutions</param> /// <returns></returns> private string RodCutSolution(int size, int[] subProblems) { string sol = string.Empty; int i = size; while (i >= 1) { sol += subProblems[i] + ", "; i = i - subProblems[i]; } return sol; }
Above we just used one one array one to store results of sub-problems and other one to store break point at maximum profit of a sub-problem(which gives actually where to cut), above method returns two objects one is maximum profit and other one output of below RodCutSolution which backtracks subProblems array to find cuts and return results in a string. We can call above method from our public method like:
public object PrintDynamicProgrammingButtomUpFullSolution() { return ButtomUpCutRodExtended(_rodSize, _sellingPrize); }
So above code will give us full solution which we will get by calling it from Main method:
static void Main(string[] args) { RodCuttingManager problem = new RodCuttingManager(10, new int[] { 0, 2, 6, 5, 7, 12, 13, 16, 15, 20, 21 });
object prof = problem.PrintDynamicProgrammingButtomUpFullSolution(); PropertyInfo[] infos = prof.GetType().GetProperties(); foreach (PropertyInfo p in infos) { Console.WriteLine(p.Name + ": " + p.GetValue(prof)); }
Console.ReadLine(); }
Output will be of our problem:
MaxProfit: 30
Solution: 2, 2, 2, 2, 2,
Analysis
We have seen four ways to solve this problem, but 1st one is not optimized, other three methods which are optimized and last one gives us full solution, If we consider 4th one for complexity calculation we can see method ButtomUpCutRodExtended having two loops one goes 1 to n which creates size of a sub problem which is "i" and inner loop goes from 1 to i. So we can see iterations will be sum:
f(n) = 1+2+3....+n = n(n+1)/2 = (n2 + n)/2
and simply we can say out complexity function:
T(n) = (n2 + n)/2 + c
but this function calls one more function which is RodCutSolution where while loop's execution depends on array subProblems but we know maximum it can occur by n times so roughly we say
T(n) = (n2 + n)/2 + n + c
Above will give us complexity is O(n2) for this method but using brute force there will we be having 2n-1 combinations and complexity will be O(2n-1) which is more than this optimized solution.
Comments: