1. Introduction

The Rod Cutting Problem is a classic optimization problem that is often solved using dynamic programming. Given a rod of length n and a list of prices for different lengths of rods, the objective is to determine the best way to cut the rod into smaller rods to maximize the total selling price. The challenge lies in deciding the lengths of pieces to cut in order to maximize profit.

2. Program Steps

1. Initialize an array val[] of size n + 1 where val[i] is the maximum value obtainable by cutting up the rod of length i.

2. Set val[0] to 0. This means a rod of length 0 has no value.

3. For each length i, compute val[i] by going through all possible cuts and picking the maximum value obtainable.

4. Return val[n] as the maximum value obtainable for the rod of length n.

3. Code Program

public class RodCutting {
    public static int cutRod(int[] prices, int n) {
        int[] val = new int[n + 1];
        val[0] = 0;

        for (int i = 1; i <= n; i++) {
            int max_val = Integer.MIN_VALUE;
            for (int j = 0; j < i; j++) {
                max_val = Math.max(max_val, prices[j] + val[i - j - 1]);
            }
            val[i] = max_val;
        }
        return val[n];
    }

    public static void main(String[] args) {
        int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};
        int n = prices.length;
        System.out.println("Maximum obtainable value is " + cutRod(prices, n));
    }
}

Output:

Maximum obtainable value is 22

4. Step By Step Explanation

1. The cutRod function takes in prices (an array containing the prices of rods for different lengths) and n (the total length of the rod) as parameters.

2. The val array is initialized to store the maximum value obtainable for each length from 0 to n.

3. The outer loop runs from 1 to n, representing the current length of the rod being considered.

4. The inner loop runs from 0 to the current length. For each possible cut length, it computes the value obtainable by adding the price of the cut to the best value of the remaining length.

5. After all possible lengths are considered, val[n] will contain the maximum value obtainable for the entire rod.

6. In the main function, a sample prices array is provided, and the cutRod function is called to compute the maximum obtainable value.