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

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.

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.

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.