Rucksackproblem Beispiel

Montanist · 23. November 2017

Hallo,

ich habe erst diese Woche mit dem rekursiven Programmieren begonnen und verstehe es leider noch nicht ganz.
Mir wurde auf der Uni folgende aufgabe gestellt:

Gegeben sind Arbeitsaufträge unterschiedlicher Dauer. Die benötigte Anzahl von Stunden für
jeden Auftrag ist in einem int-Array hinterlegt. Schreiben Sie die public-Klasse ueb.Auftraege
mit einem parameterlosen Konstruktor und der Methode
public static int getMaxAnzahl(int[] auftragslaengen, int maxStunden),
die die maximale Anzahl der Aufträgen zurückliefert, die in maxStunden erledigt werden
können. (Die Aufträge, die erledigt werden, können beliebig aus den gegebenen Aufträgen
gewählt werden.)

ja ich weiß, iterativ ist dieses Beispiel schnell zu lösen allerdings brauch ich einen rekursiven Lösungsweg.
In der Vorlesung haben wir das Rucksackproblem durchgemacht weshalb ich diesn Ansatz genommen und ausgebaut habe:

Code:

import java.util.*;
public class Auftraege
{
    
    public Auftraege()
    {
    }
    private static ArrayList<Integer> zeiten;
    public static int getMaxAnzahl(int[] auftragslaengen, int maxStunden)
    {
       zeiten = new ArrayList<Integer>();
       for(Integer a: auftragslaengen)
       {
           zeiten.add(a);
       }
       List<Integer> ziel = auswahl(0,zeiten,maxStunden);
       return ziel.size();
    }
     public static List<Integer> auswahl(int k, ArrayList<Integer> zeiten, int restStd)
     {

         if(k >= zeiten.size())
         {
             return new ArrayList<>();
         }
         List<Integer> ohne =auswahl(k+1, zeiten, restStd);
         Integer a = zeiten.get(k);
         if(a <= restStd)
         {
             List<Integer> mit = auswahl(k+1, zeiten, restStd - a);
             mit.add(a);
             if(mit.size() > ohne.size())
             {
                 return mit;
             }
         }
         return ohne;
     }
     
     public static int max(List<Integer> x)
     {
         int summe = 0;
        for(Integer a: x)
        {
            summe += a;
        }
        return summe;
    }

Der Code funktioniert allerdings dauert diese Lösung beim Ausführen zu lange, habt ihr Vorschläge dieses Beispiel eleganter zu lösen?

LG

asdfman · 23. November 2017

Das Rucksackproblem ist ein Standardbeispiel für ein "schweres" Problem, was den rechnerischen Aufwand angeht. Vielleicht ist die Erkenntnis, dass es lange dauert ja auch der Sinn der Übung?

Andreas_ · 23. November 2017

Die Aufgabenstellung ist hier doch gar nicht das Rucksackproblem?

Schreiben Sie die public-Klasse ueb.Auftraege mit einem parameterlosen Konstruktor und der Methode public static int getMaxAnzahl(int[] auftragslaengen, int maxStunden), die die maximale Anzahl der Aufträge zurückliefert, die in maxStunden erledigt werden können.

Nach meinem Verständnis wäre das Rucksackproblem hier, wenn man die Arbeitsaufträge finden sollte, mit denen maxStunden möglichst vollständig ausgenutzt wird.

Für die Aufgabe, die maximale Anzahl von Arbeitsaufträgen zu bestimmen, reicht es, die Arbeitsaufträge nach benötigter Zeit aufsteigend zu sortieren und dann vom ersten beginnend die Zeiten zu addieren bis maxStunden erreicht ist. Alternativ geht das natürlich auch ohne Sortierung, wenn man jedesmal den Arbeitsauftrag mit der kleinsten Zeit unter den verbliebenen Arbeitaufträgen bestimmt und addiert.

Krafty · 23. November 2017

Ich habe das auch wie Andreas_ verstanden.

Um es rekursiv zu lösen, hast du die Klasse mit der Methode getMaxAnzahl() und ihren beiden Parametern und eventuell eine private Zählervariable (default 0).

Du erzeugst außerhalb das Array mit den Aufträgen, übergibst das zusammen mit der Anzahl der maximalen Stunden an die Methode.
In der Methode sortierst du das, schaust dir das erste Element an, wenn die Zeit größer maxStunden ist, dann returnst du die Zählervariable.

Anderenfalls zählst du die Zählervariable 1 hoch, ziehst von maxStunden die Zeit aus dem ersten Element ab, entfernst das erste Element und rufst die Methode in sich selbst mit den geänderten Werten wieder auf.

Drexel · 23. November 2017

Ja es macht keinen Sinn, das rekursiv zu lösen, das bringt bei dieser Aufgabe keinen Vorteil. Nichtmals wenn die Aufträge unterschiedliche Werte hätten. Ich finde Deinen Quelltext auch schwierig zu lesen, kein einziger Kommentar und keine sprechenden Bezeichner für die Variablen. Da fällts mir gerade ohne Debugger sehr schwer das nachvollziehen.

Typischere Probleme wo eine Rekursion sinnvoller ist sind die Säulen von Hanoi oder das auslesen aller Verzeichnisse auf einer Festplatte z.B..

Ergänzung (23. November 2017)

Krafty schrieb:
Ich habe das auch wie Andreas_ verstanden.

Um es rekursiv zu lösen, hast du die Klasse mit der Methode getMaxAnzahl() und ihren beiden Parametern und eventuell eine private Zählervariable (default 0).

Du erzeugst außerhalb das Array mit den Aufträgen, übergibst das zusammen mit der Anzahl der maximalen Stunden an die Methode.
In der Methode sortierst du das, schaust dir das erste Element an, wenn die Zeit größer maxStunden ist, dann returnst du die Zählervariable.

Anderenfalls zählst du die Zählervariable 1 hoch, ziehst von maxStunden die Zeit aus dem ersten Element ab, entfernst das erste Element und rufst die Methode in sich selbst mit den geänderten Werten wieder auf.

Stimmt so könnte man das einfacher rekursiv lösen, für sinnvoll halte ich das aber wegen Lesbarkeit etc immer noch nicht.

Montanist · 23. November 2017

Hallo,

danke für die schnellen Antworten. Meine erste variante bestand natürlich auch darin das Array zu sortieren und so lange zusammen zu zählen bis die maxStunden erreicht wurden dann einen zähler ausgeben, aller dings will mein Prof eine rekursive Lösung. Nachdem wir bis jetzt nur das Rucksackproblem in der Vorlesung besprochen haben habe ich das verwendet und erweitert was zwar zum richtigen ergebnis führt aber viel zu unübersichtlich und aufwendig ist....

Krafty schrieb:
Ich habe das auch wie Andreas_ verstanden.

Um es rekursiv zu lösen, hast du die Klasse mit der Methode getMaxAnzahl() und ihren beiden Parametern und eventuell eine private Zählervariable (default 0).

Du erzeugst außerhalb das Array mit den Aufträgen, übergibst das zusammen mit der Anzahl der maximalen Stunden an die Methode.
In der Methode sortierst du das, schaust dir das erste Element an, wenn die Zeit größer maxStunden ist, dann returnst du die Zählervariable.

Anderenfalls zählst du die Zählervariable 1 hoch, ziehst von maxStunden die Zeit aus dem ersten Element ab, entfernst das erste Element und rufst die Methode in sich selbst mit den geänderten Werten wieder auf.

Das war auch mein erster Gedanke und habe es versucht, allerdings bin ich Neuling im rekursiven Programmieren und schaffe die richtige schreibweise noch nicht.... Habe eine Abbruchbedingung gemacht, wenn die maxStunden erreicht sind soll er den Zähler zurück geben, in der Rekrusion verringert er die Stunden und erhöht den Zähler, da ich es aber noch nicht 100%ig durschschaut habe bin ich zu keiner richtigen Lösung gekommen, könnt ihr mir bei dem Code evtl. helfen?

Krafty · 23. November 2017

Ich bin leider nicht besonders fit in Java Syntax.

Woran hapert es denn?
this.getMaxAnzahl(neuesAuftragslaengen, maxStunden - auftragslaengen[0]) in der Methode sollte doch tun?

Suche

Rucksackproblem Beispiel

Montanist

Newbie

asdfman

Commander

Andreas_

Commander

Krafty

Lt. Commander

Drexel

Lt. Commander

Montanist

Newbie

Krafty

Lt. Commander

Ähnliche Themen