# Solving the rod-cutting problem using dynamic programming

Posted on

Problem

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++) {
}
Collections.sort(cutLengths);
List<List<Integer>> optimalCuts = new ArrayList<List<Integer>>();

// initialize list
for (int i = 0; i <= length; i++) {
}

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

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

public static void main(String[] args) {
int[] cuts = { 1, 3, 4, 7 };
int rodLength = 100;
RodCutting cut = new RodCutting(cuts, rodLength);
}
}
``````

Solution

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++) {
}
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++) {
}

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

for (int i = 0; i < optimalCuts.size(); i++) {
System.out.println(i + ": " + optimalCuts.get(i));
}

}

// ... rest of the code
``````