使用回溯功能将军事单位最佳地装载到船上

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");
}

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

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

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

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

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

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
...