Rod Cutting Problem – Dynamic Programming
Given a rod of size n and values of various sizes of rod. The problem is to cut the rod in such a way that the sum of values of the pieces is maximum.
For e.g.
var arr = {2, 3, 7, 8, 10}
will consider size of rod is length of arr here i.e.5.
Size’s of the road are 1,2,3,4,5 respectively.
So, we can cut the rod in various ways like
{2, 8}
{3, 7}
{2, 2, 2, 2, 2}
{2, 2, 7}
To get the maximum profit we will cut the rod {2, 2, 7}
Solution using Dynamic programming:
The problem can be solved by calculating the maximum combination value of rod by cutting in various pieces in a bottom up fashion by first calculating for smaller value of n and then using these values to calculate higher values of n.
The time complexity of this solution is O(n^2).
using System;
namespace Rod{
class Program
{
static void Main()
{
var arr = new int[] { 2, 3, 7, 8, 10 };
var result = RodCutting(arr);
Console.WriteLine($"Maximum sum of the values is {result} ");
Console.ReadLine();
}
static int RodCutting(int[] arr)
{
var result = new int[arr.Length + 1];
result[0] = 0;
for (var i = 1; i <= arr.Length; i++)
{
result[i] = int.MinValue;
for (var j = 0; j < i; j++)
{
result[i] = Math.Max(result[i], arr[j] + result[i - (j + 1)]);
}
}
return result[arr.Length];
}
}
}