Cacher is the code snippet organizer for pro developers

import java.util.*;


/**
example for cutting a resource of length l in given denominations in an optimal way
The running time is O(numberofdenominations*l) the auxilary space complexity is order of length

There is possibbly some amount of resource left unused depending on denominations.

You can play with denominations.
*/

public class CuttingRod{

  static RodDenomination [] denominations = {
    // new RodDenomination(1,2),
    new RodDenomination(2,5),
    new RodDenomination(3,7),
    new RodDenomination(4,8),
    new RodDenomination(18,49)
  };

  public static void main(String... args){
    for(int i = 5 ; i < 20 ; i++){
      ResourcePartitioning partitioning = maxValueOfPiece(denominations, i);
      System.out.println("Max value of length " + i + " is "+partitioning.totalValue+
      ". Pieces are " + partitioning.partLengths);
    }
  }

  public static ResourcePartitioning maxValueOfPiece(RodDenomination[] denominations , int length){
    ResourcePartitioning partitioning = new ResourcePartitioning();
    int [] bestVal = new int[length+1];//best value attainable by the length
    int [] prev = new int[length+1];//pointer to the length of remaining piece after cut
    for(int i = 0 ; i <= length ; i ++)
    {
      for(RodDenomination d : denominations){
        int reach =i+ d.length;// the next point
        if(reach <= length &&  bestVal[i] + d.value > bestVal[reach]){
          bestVal[reach] = bestVal[i] + d.value;
          prev[reach] = i;
        }
      }
    }
    partitioning.totalValue = bestVal[length];
    while(bestVal[length ] > 0){
      int biggerPiece = prev[length];
      partitioning.partLengths.add(length - biggerPiece);
      length = biggerPiece;
    }
    return partitioning;
  }

  private static class ResourcePartitioning{
    int totalValue;
    List<Integer> partLengths = new ArrayList<>();
  }

  private static class RodDenomination{
    int length;
    int value;
    private RodDenomination(int length , int val){
      this.length = length;
      value = val;
    }
  }

}