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);
    }
}

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