Loading military units into ships optimally, using backtracking

Question

I solved the following problem using backtracking:

We are given a list of military units, their weight and their (numerical) strength. We have a number of ships with a limited carrying capacity. Determine how to load ships with military units, so that carrying capacity for each ship is not exceed and so that we have the maximum possible military strength on our ships.

However, my code is not fast enough, as there are many unnecessary calculations being done, that does not lead to a solution. How would I optimize my code? My idea is to use memoization, but how would I implement it?

I tried to comment my code and refactor my code as best as I can.

public class HeroesOntTheBoat {

private int[] arrayWithGeneratedNumbers;
private int numberOfShips;
private int max;
private int[] bestArray;
private ArrayList<Integer> strengths;
private ArrayList<Integer> weights;
private ArrayList<Integer> carryingCapacities;

public HeroesOntTheBoat() {
    carryingCapacities = new ArrayList<Integer>(); // create arraylist for the carrying capacities of ships
    strengths = new ArrayList<Integer>(); //create arraylists for strengths and weights of units
    weights = new ArrayList<Integer>(); //create arraylists for weights
    max = 0; // global variable max for finding the best strength
}

private void generate(int fromIndex) { // I generate all combinations between 0 and numberOfShips
    if (fromIndex == arrayWithGeneratedNumbers.length) { // 0 is representing that unit is being left behind
        processGeneratedNumbers();      // 1,2,3,4..n are representing the number of ship that the unit is loaded on
        return;                         // index of a number in array is representing a specific unit               
    }

    for (int i = 0; i <= numberOfShips; i++) {
        arrayWithGeneratedNumbers[fromIndex] = i;
        generate(fromIndex + 1);
    }
}

public void input(String input) {
    Scanner sc = null;
    try {
        sc = new Scanner(new File(input)); // load my input from a textfile
        numberOfShips = sc.nextInt();  // load the number of ships
        for (int i = 0; i < numberOfShips; i++) { //add carrying capacities to arraylist
            carryingCapacities.add(sc.nextInt());
        }
        bestArray = new int[weights.size()]; // array where we will remember the best combination of units
        while (sc.hasNext()) {
            weights.add(sc.nextInt());
            strengths.add(sc.nextInt());
        }
        arrayWithGeneratedNumbers = new int[weights.size()]; // array where we will generate numbers
        generate(0); // run the generation
        System.out.println(Arrays.toString(bestArray) + " this is the best layout of units"); // after the generation is over
        System.out.println(max + " this is the max strength we can achieve"); // print the results
    } catch (FileNotFoundException e) {
        System.err.println("FileNotFound");
    } finally {
        if (sc != null) {
            sc.close();
        }
    }
}

public void processGeneratedNumbers() {
    int currentStrength = 0; // process every generated result
    boolean carryingCapacityWasExceeded = false;
    int[] currentWeight = new int[numberOfShips + 1];
    for (int i = 0; i < arrayWithGeneratedNumbers.length; i++) { // calculate weights for every ship and ground
        currentWeight[arrayWithGeneratedNumbers[i]] += weights.get(i);
    }
    for (int i = 0; i < currentWeight.length; i++) { // is capacity exceeded?
        if (i != 0 && currentWeight[i] > carryingCapacities.get(i - 1)) { // ignore 0, because 0 represents ground(units I left behind)
            carryingCapacityWasExceeded = true;
        }
    }
    if (carryingCapacityWasExceeded == false) { // if capacity isn't exceeded
        for (int i = 0; i < arrayWithGeneratedNumbers.length; i++) { // calculate strength
            if (arrayWithGeneratedNumbers[i] != 0) { // ignore 0, because I left units with 0 behind on the ground
                currentStrength += strengths.get(i);
            }
        }
        if (currentStrength > max) { // is my current strength better than global maximum?
            max = currentStrength; // replace my global maximum
            bestArray = arrayWithGeneratedNumbers.clone(); // remember the new best layout of units
        }

    }

}


public static void main(String[] args) {
    HeroesOnTheBoat g = new HeroesOnTheBoat();
    g.input("inputFile");
}

Example input:

2 60 40
30 400
20 500
50 100
40 100
30 50
60 75
40 20

and its result:

[1, 1, 0, 2, 0, 0, 0] this is the best layout of units
1000 this is the max strength we can achieve

Answer 1

The algorithm

This algorithm creates every combination of ships and tests them one by one, including combinations that could be seen to be useless by the first choice made. For example, if the first choice is to assign a unit of weight 60 to a ship with capacity 50, then it no longer matters what the rest of the content of arrayWithGeneratedNumbers will be, there is no point recursively calling generate when there is already such a problem.

The solution to that is checking as much as possible as early as possible. So in generate, do not only check the solution when it is fully formed, check for capacity violations every time. That seems like more wasted work, but it's not a waste, it prevents a ton of recursion. If a capacity check fails early, thousands maybe millions of combinations will be skipped, by simply not generating them.

For example like this, using the names from below:

private void generateAssignments(int fromIndex) {
    if (!isValidAssignment(unitAssignment))
        return;
    ...

Or like this:

for (int i = 0; i <= numberOfShips; i++) {
    unitAssignment[fromIndex] = i;
    if (isValidAssignment(unitAssignment))
        generateAssignments(fromIndex + 1);
}

A similar related trick is computing the strength early, and returning back up the recursion tree once you see that the current branch cannot result in a better solution than some solution that you already have. So this only works if there is some non-trivial solution already, and it is useful to do a simple greedy pass first to initialize with, so more of the recursion is pruned right from the start.

For example:

private void generateAssignments(int fromIndex, int currentStrength, int remainingStrength) {
    if (currentStrength + remainingStrength <= bestStrengthSoFar)
        return;

Where currentStrength is the sum of strengths of units that have been assigned to ships, and remainingStrength is the sum of strengths of units for which no choice has been made, both can be maintained easily when choices are made. That's a pretty naive technique that does not take weights into account, which you could do, for example taking the unit with the best strength-to-weight ratio for which no choice has been made, and set the remaining strength to (double)remainingCapacity / unitWeight * unitStrength, in essence pretending that you can fill all of the remaining capacity with the best possible unit even it it needs to be cloned and cut into pieces.

With pruning, the order in which choices are made matters: pruning near the root of the tree is orders of magnitude better than pruning near the leafs. A general rule of thumb is to pick the most-constrained item first, and try the least-constraining choice for it first. So in this domain, pick the heaviest unit, and put it on the biggest ship. However, we can also make use of the strengths and go for units with a high strength-per-weight ratio first, relying on the idea of filling the ships with good units first and then trying to "fill the gaps" with worse units. There are different strategies here, probably almost anything is better than not using a strategy.

Naming

There are several extremely generic names in this code, bordering on meaninglessness. generate, generate what? processGeneratedNumbers, what is process? What are "generated numbers"? arrayWithGeneratedNumbers, variable names shouldn't repeat their type and again what are "generated numbers". This is not an abstract domain where we don't know what is being generated or what the numbers mean, the data here has a specific meaning, and the methods do specific things. So you could use names such as:

• unitAssignment, in the sense of assigning units to ships. Or shipAssignment, in the same sense.
• isAssignmentValid, checkCapacities, something like that. That's for the version that does not also update the best-solution-so-far, just pure checking for the purpose of pruning.

Also I wouldn't put the unrelated input between two related methods.

Boolean flag logic

Always a contentious point, but I would say, as a rough approximation, the fewer boolean flags the better. Return when the first checks fails, no messy business with flags.

Answer 2

Write useful comments

carryingCapacities = new ArrayList<Integer>(); // create arraylist for the carrying capacities of ships
strengths = new ArrayList<Integer>(); //create arraylists for strengths and weights of units
weights = new ArrayList<Integer>(); //create arraylists for weights
sc = new Scanner(new File(input)); // load my input from a textfile
numberOfShips = sc.nextInt();  // load the number of ships
for (int i = 0; i < numberOfShips; i++) { //add carrying capacities to arraylist
...

All these comments (and pretty much all the others too, I left them out for brevity) are redundant english language explanations of what the code does. They add no value. Instead they make the code harder to read by interrupting the code.

When people say code should be self documenting, it means the code should tell you what it does. This is done by using names that describe what a field contains or what a method does (and you've got that nailed down pretty well). Comments should not repeat that, instead the comments should explain why the code does what it does because that is something that cannot sometimes be expressed with code only.

There is no need to explain that data is read from a file when you have code that declares a scanner and a file, or that an ArrayList is being created when you call new ArrayList<>().´

Also, end-of-line-comments are the hardest ones to read, write and maintain. Avoid them.

Answer 3

It appears that you've massively underestimated the complexity of the task. This is a classic Multiple Knapsack problem, and as is the case with all NP-hard problems, the time to solve it and/or the required memory grows very, very, very, very fast with the input size.

The choice of algorithm is crucial. It makes no sense to polish the code if the algorithm is poorly chosen, and naive iteration is no good.

If you are really interested in such problems and have some time to spare, I would highly recommend the course "Discrete Optimisation" on Coursera. The (single) Knapsack problem is covered in Week 2 videos. For me, the approach that worked best was the one described in "Knapsack 5 - relaxation, branch and bound". Basically, the algorithm works this way:

1. You make a choice, e.g. which boat to put Unit 1 on, or not at all. Or which unit to put on Boat 1 first. You have a choice of choices, isn't it cool already?
2. For each choice you estimate the worst and the best outcome. For your problem, the worst outcome may be a fast greedy solution of the remaining task, and the best outcome is the greedy fractional solution: you imagine that a unit may be split and its part will have the proportional value.
3. If the best outcome of one choice is worse than the worst outcome of another, you may safely discard that option. Otherwise, choose the most attractive branch (it might be useful not to choose the one with the best possible outcome, but to introduce a certain randomness) and repeat steps 1-3.

Eventually (actually, quite fast) you'll get one probable solution. It won't be the best (it might be, but for a sufficiently large size it's improbable). The simplest way to go on would be to try the next branches immediately (depth-first tree search), it is achievable by a simple recursion and is almost free for you as a developer. However, this is a suboptimal approach: you'll spend a lot of time in one branch of solution tree, while the solution is as likely to be somewhere else. It pays off to have a smarter search strategy, to be able to go back further and branch from an earlier state. You'll need to have some data structure to keep track of what you've already checked. Take care that it doesn't eat all your memory, that's what it really likes to do.

A nice benefit of such approach, shared by most practical algorithms for NP-hard problems, is that for tasks that are too huge to find the optimal solution it may still get you a good enough solution, if you stop it before the time limit is reached.

Have fun!