Multiple Choice Knapsack- Problem

Diskutiere Multiple Choice Knapsack- Problem im Allgemeine Java-Themen Bereich.
1

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?


Java:
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

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

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

Multiple Choice Knapsack- Problem

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben