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 |