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];
        }
    }
    
}