2
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – rolfl Jan 29 '15 at 1:13
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.