Frage
24.08.2016, 13:59
Wie programmiere ich das Rucksackproblem rekursiv?

Hallo, ich muss für die Uni ein paar Aufgaben programmieren, die meisten habe ich schon, aber nun muss ich das Rucksackproblem rekursiv lösen und habe einen vorgegebenen Methodenkopf:

public static int backtrackingCalculation(List items, int capacity) {}

Im Internet finde ich keine ähnlichen Fälle, da diese immer andere Parameter übergeben dürfen und nun komme ich einfach nicht weiter. Ich sitze schon mehrere Stunden an dieser Methode und habe noch nicht einmal eine Zeile geschafft, da ich keinen Ansatz habe.

Die Liste items, enthält die items die ich benutzen muss. Jedes Item hat einen Wert und ein Gewicht, diese bekomme ich mit getValue und getWeight. Int capacity beschreibt die Menge, die der 'Rucksack' maximal tragen kann. Der Rückgabewert ist vom typ int und soll den Wert (value) enthalten.

Was ich bisher herausgefunden habe ist, dass man jede mögliche Kombination der Items durchgehen muss und immer die bessere Kombination zurückgeben soll, aber ich habe keine ahnung wie ich das machen soll.

Ich muss bis Samstag Abend fertig sein und habe nun schon etliche Internet-Seiten durch, finde aber nichts, was mich weiterbringt.

Vielen Danke schonmal im voraus!!

 ...zur Frage
Antwort
24.08.2016, 16:37 
    public static int backtrackingCalculation(List items, int capacity) {

        int with = 0;

        int without = 0;

        int capa = capacity;


        while (items.size() > 0) {


            if (items.get(0).getWeight() < capacity) {

                with += items.get(0).getValue();

                capacity -= items.get(0).getWeight();

                items.remove(0);

                with += backtrackingCalculation(items, capacity);

                without += backtrackingCalculation(items, capa);

            } else {

                items.remove(0);

                with+= backtrackingCalculation(items, capacity);

                without += backtrackingCalculation(items, capa);

            }


        }


        if (without > with) {

            return without;

        }

        return with;


    }

Habe eine neue Variante. Ich habe versucht jede mögliche Kombination durchrechnen zu lassen und die Beste dann auszusuchen.

with bedeutet ich nehme das item mit rein und without bedeutet ich nehme es nicht mit rein.

Aber auch das funktioniert nicht. Es berechnet zwar einiges aber das richtige Ergebnis wird auch nicht gefunden.

 ...zur Antwort