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