Write a program to find the maximum value obtainable by cutting up the rod and selling the pieces. Rod length is N
source Code
package com.dsacode.Algorithm.dynamic;
import java.util.Arrays;
public class RodCutting {
public int RodCut(int p[], int n) throws Exception{
if(n >= p.length ){
throw new Exception("rod of length can not grater than the price array length");
}
if (n == 0) {
return 0;
}
int q = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++) {
q = Math.max(q, (p[i] + RodCut(p, n - i)));
}
return q;
}
public static void main(String args[]) throws Exception {
int[] p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
System.out.println("Array of items: " + Arrays.toString(p));
int n = 5;
System.out.print("Rod Length = "+n+" and solution = ");
RodCutting rd = new RodCutting();
int y = rd.RodCut(p, n);
System.out.print(y+"\n");
}
}
Output
Array of items: [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30] Rod Length = 5 and solution = 13
Algorithm Explanation
 | Get the array of items and number of rod length. |
| Check the rod length with price array length. If the rod length more than price length, throw an exception. |
| If the rod length is 0, return the function. |
| Use Math max function to cut the road recursively |
| Return the length and print the value |