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
|
static void Main(string[] args) { int[] price = new int[] { 1, 5, 6, 9, 10 }; int length = price.Length; Console.WriteLine("Total Profit is :- " + Class1.TotalProfitToCutRod(price, length));
} public static int TotalProfitToCutRod(int[] p, int n) { int[] r = new int[n + 1]; r[0] = 0;
for (int j = 1; j <= n; j++) { int q = int.MinValue; for (int i = 1; i <= j; i++) { q =
Math.Max(q, p[i - 1] + r[j - i]); } r[j] = q; } return r[n]; } |
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
|
static void Main(string[] args) { int[] price = new int[] { 1, 5, 6, 9, 10 }; int length = price.Length; Console.WriteLine("Total Profit is :- " + Class1.TotalProfitToCutRod(price, length));
} public static int TotalProfitToCutRod(int[] p, int n) { if (n <= 0) return 0; int maximum_val = int.MinValue;
for (int i = 0; i < n; i++)
maximum_val = Math.Max(maximum_val, p[i] + TotalProfitToCutRod(p, n - i - 1));
return maximum_val; } |
----------------------------------------------------------------
