Solving the rod-cutting problem using dynamic programming

Question

I've written what I believe is a valid dynamic programming solution to a variation of the rod cutting problem. In this problem, the goal is to make as few cuts as possible on a rod of length n.

I have two questions:

1. Is this a valid dynamic programming solution?
2. How can it be improved?

(This is not a school assignment. I simply want to understand dynamic programming better)

public class RodCutting {
 RodCutting(int[] cuts, int length) {
 List<Integer> cutLengths = new ArrayList<Integer>();
 for (int i = 0; i < cuts.length; i++) {
 cutLengths.add(cuts[i]);
 }
 Collections.sort(cutLengths);
 List<List<Integer>> optimalCuts = new ArrayList<List<Integer>>();
 // initialize list
 for (int i = 0; i <= length; i++) {
 optimalCuts.add(new ArrayList<Integer>());
 }
 for (int i = 1; i <= length; i++) {
 // assume 1 is always a valid cut length
 if (cutLengths.contains(i)) {
 for (int j = 0; j < cutLengths.size(); j++) {
 if (i == cutLengths.get(j)) {
 optimalCuts.get(i).add(cutLengths.get(j));
 // nothing larger than the current cut
 }
 }
 } else {
 for (int j = 0; j < cutLengths.size(); j++) {
 if (i > cutLengths.get(j)) {
 List<Integer> newCuts = union(
 optimalCuts.get(i - cutLengths.get(j)),
 cutLengths.get(j));
 if (optimalCuts.get(i).size() == 0
 || newCuts.size() < optimalCuts.get(i).size()) {
 optimalCuts.remove(i);
 optimalCuts.add(i, newCuts);
 }
 }
 }
 }
 }
 for (int i = 0; i < optimalCuts.size(); i++) {
 System.out.println(i + ": " + optimalCuts.get(i));
 }
 }
 List<Integer> union(List<Integer> listOfCuts, int additionalCut) {
 List<Integer> returnList = new ArrayList<Integer>(listOfCuts);
 returnList.add(additionalCut);
 return returnList;
 }
 public static void main(String[] args) {
 int[] cuts = { 1, 3, 4, 7 };
 int rodLength = 100;
 RodCutting cut = new RodCutting(cuts, rodLength);
 }
}

• rolfl: Please update your question with a definition of what you think the rod-cutting algorithm is, your code does not support a concept of a price, and that's normally core to the problem. Am I missing something?

Answer 1

I'm not familiar with the problem of rod-cutting, so I cannot reflect on the correctness of the algorithtm. However, I can give you suggestions for some slight improvements:

1. union method does not depend on any instance variables --> consider making it static

2. consider splitting the algorithm into two parts: the constructor could have just some code to store the parameters, and then you could have a separate method to perform the actual calculations (this would make the code more readable)

So, I suggest something like this (not tested):

public class RodCutting {
 private int [] cutLengths;
 private int length;
 RodCutting(int[] cuts, int length) {
 cutLengths = new ArrayList<Integer>();
 for (int i = 0; i < cuts.length; i++) {
 cutLengths.add(cuts[i]);
 }
 Collections.sort(cutLengths);
 this.length = length;
 }
 public void calc() {
 List<List<Integer>> optimalCuts = new ArrayList<List<Integer>>();
 // initialize list
 for (int i = 0; i <= length; i++) {
 optimalCuts.add(new ArrayList<Integer>());
 }
 for (int i = 1; i <= length; i++) {
 // assume 1 is always a valid cut length
 if (cutLengths.contains(i)) {
 for (int j = 0; j < cutLengths.size(); j++) {
 if (i == cutLengths.get(j)) {
 optimalCuts.get(i).add(cutLengths.get(j));
 // nothing larger than the current cut
 }
 }
 } else {
 for (int j = 0; j < cutLengths.size(); j++) {
 if (i > cutLengths.get(j)) {
 List<Integer> newCuts = union(
 optimalCuts.get(i - cutLengths.get(j)),
 cutLengths.get(j));
 if (optimalCuts.get(i).size() == 0
 || newCuts.size() < optimalCuts.get(i).size()) {
 optimalCuts.remove(i);
 optimalCuts.add(i, newCuts);
 }
 }
 }
 }
 }
 for (int i = 0; i < optimalCuts.size(); i++) {
 System.out.println(i + ": " + optimalCuts.get(i));
 }
 }
// ... rest of the code