Multiple Choice Knapsack- Problem

[14chris2]

Hallo Leute ,

ich habe hier ein Problem mit meinem Multiple Choice Knapsack und sitze seit 3h fest.
Mein Problem ist, dass: weight = Integer.MAX_VALUE-1 gesetzt wird.

Ich habe rumprobiert, kam aber auf keine machbare Lösung.
Ich muss den Array kanpsack so erstellen, dass weight passt (also die +1 muss weg) und ich muss ebenfalls die for-Schleifen so anpassen,
dass die Berechnung weiter funktioniert.

Habt ihr Tipps/Vorschläge/ähnliche Erfahrungen, die helfen, dass der Array nicht java.outOfBounds ist?

public static int MCKS(final ItemGroup[] itemGroups, final int weight) {

        if (weight <= 0 || itemGroups == null || itemGroups.length == 0) {
            throw new IllegalArgumentException("Failure.");
        }
        int i, w = 0;

        int[][] knapsack = new int[itemGroups.length + 1][weight + 1];

        for (int a = 0; a <= weight - 1; a++) {
            knapsack[0][a] = 0;
        }
        for (i = 1; i <= itemGroups.length; i++) {
                for (w = 0; w <= weight; w++) {

                    if (w >= 0) {
                        if (itemGroups[i - 1].getItems().get(0).getWeight() > w) {
                            knapsack[i][w] = knapsack[i - 1][w];

                        } else {
                            knapsack[i][w] = max(
                                    itemGroups[i - 1].getItems().get(0).getProfit()
                                            + knapsack[i - 1][w - itemGroups[i - 1].getItems().get(0).getWeight()],
                                    knapsack[i - 1][w]);
                        }
                    }
                }
            }
        return knapsack[itemGroups.length][weight];
    }
}

Viele Grüße

 

[Blender3D]

knapsack[i - 1][w - itemGroups[i - 1].getItems().get(0).getWeight()],

Falls getWeight() einen größeren Wert als w liefert bekommst Du einen negativen Index --> Out of Bounds.
Falls getWeight() z.B. -1 zurück gibt und w den letzten Index beinhaltet --> Out of Bounds

 

[mihe7]

Mein Problem ist, dass: weight = Integer.MAX_VALUE-1 gesetzt wird.

Dein Problem ist, dass Du ein zweidimensionales Array verwendest. So, wie ich das MCKP verstehe, habe im Rucksack genau itemGroups.length Gegenstände Platz, deren Gewichte in Summe weight nicht übersteigen dürfen.