Dot Net Office: Rod Cutting Problem in C#

Rod Cutting Problem in C#

The rod-cutting problem is the classic dynamic programming problem. In this problem, we cut a rod of a given length into smaller pieces with certain prices for each piece.

As per this problem, we need to determine the maximum revenue profit that can be get by cutting up the rod and selling the pieces of rod.

Problem statement

Given a rod of length n and we need to cut the rod in such a way that we need to sell it for the maximum revenue profit. We also have the price table, which tells us the worth of the rod.

Length =	1	2	3	4	5
Price =	1	5	6	9	10

So, according to the above table, if we cut the rod of length 1 we can sell it for $1.

Similarly, if we cut the rod at length 2, we can sell it at $5 and if we cut the rod at length 3, we can sell it at $6.

According to the problem, we need to find a way, how to cut the rod so that we can get maximum profit.

Here rod length is 5, so if we give the whole rod, without cutting it so the profit is $10. But if we cut the rod at length 2 and at length 3 (so total rod size is 2+3 = 5), then the total profit will be 5 + 6 = 11. This gives us maximum profit.

Dynamic programming solution

1static void Main(string[] args) {
2 int[] price = new int[] {3 1,4 5,5 6,6 9,7 108 };
9 int length = price.Length;
10 Console.WriteLine("Total Profit is :- " + Class1.TotalProfitToCutRod(price, length));
11}
12public static int TotalProfitToCutRod(int[] p, int n) {
13 int[] r = new int[n + 1];
14 r[0] = 0;
15 for (int j = 1; j <= n; j++) {
16 int q = int.MinValue;
17 for (int i = 1; i <= j; i++) {
18 q = Math.Max(q, p[i - 1] + r[j - i]);
19 }
20 r[j] = q;
21 }
22 return r[n];
23}

In this implementation, p is the array of prices for each piece length of rod and n is the length of the rod. This function returns the maximum profit that we get by cutting up the rod.

Naive recursive solution

1static void Main(string[] args) {
2 int[] price = new int[] {3 1,4 5,5 6,6 9,7 108 };
9 int length = price.Length;
10 Console.WriteLine("Total Profit is :- " + Class1.TotalProfitToCutRod(price, length));
11}
12public static int TotalProfitToCutRod(int[] p, int n) {
13 if (n <= 0) return 0;
14 int maximum_val = int.MinValue;
15 for (int i = 0; i < n; i++) maximum_val = Math.Max(maximum_val, p[i] + TotalProfitToCutRod(p, n - i - 1));
16 return maximum_val;
17}