Dynamic programming

Rod cutting

Pinterest LinkedIn Tumblr

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

Reference

  1. http://www.radford.edu/~nokie/classes/360/dp-rod-cutting.html
  2. http://faculty.ycp.edu/~dbabcock/PastCourses/cs360/lectures/lecture12.html

Write A Comment