Sushi satt

Postkarte - Sushi

Diese Art von Rätsel ist auch als “Rucksackproblem” bekannt. Das Rucksackproblem fasst eine Klasse von Aufgabenstellungen zusammen, in denen es darum geht, bestimmte Objekte aus einer Menge auszuwählen. Jedes Objekt hat dabei verschiedene “Kosten” (manchmal auch als “Gewichte” oder “Größen” bezeichnet) und “Nutzenwerte”. Ziel ist es, eine Teilmenge mit maximalem Gesamtnutzen auszuwählen, deren Gesamtkosten eine vorgegebene Schranke (die Kapazität des namensgebenden Rucksacks) nicht überschreiten.

In diesem Fall sind die Kosten die Preise der einzelnen Sushiboxen und die Nutzenwerte die Anzahl der enthaltenen Sushistücke: Wir wollen mit unseren 15 € natürlich sowie Sushi wie möglich abstauben.

Lösung mit Aufnehmen und Zurücklegen

Wie finden wir nun die optimale Auswahl? Die naheliegendste Möglichkeit besteht darin, alle möglichen Kombinationen von Sushiboxen auszuprobieren, jeweils die Kosten und Stückzahlen zu berechnen und dann die Kombination mit der maximalen Stückzahl zu kaufen. Dazu muss man allerdings strukturiert vorgehen, um keine Kombination mehrfach auszuprobieren, keine Kombination zu vergessen und keine Kombinationen auszutesten, die Teilmengen enthalten, von denen man bereits weiß, dass sie zu teuer sind.

Dazu sortieren wir als erstes die verschiedenen Boxensorten nach aufsteigendem Preis und nennen sie in dieser Reihenfolge “A”, “B”, “C”, “D” und “E”:

Boxensorte: A B C D E
Preis pro Box (“Kosten”): 3€ 4€ 6€ 9€ 10€
Sushi-Stücke pro Box (“Nutzen”): 4 5 10 13 18

Für das Testen der Kombinationen gelten jetzt die folgenden Regeln:

  • Wir beginnen, indem wir eine Box der Sorte “A” aufnehmen.
  • Wir nehmen solange weitere Boxen auf, solange die Gesamtkosten unter 15 € sind.
  • Damit nimmt man als nächstes immer nur eine Box derselben Sorte wie die zuletzt aufgenommene.
  • Wenn wir 15 € erreicht oder überschritten haben, legen wir die letzten beiden Boxen zurück und nehmen eine Box der nächsthöheren Sorte als die zuletzt abgelegte auf und machen wie vorher weiter.
  • Wenn wir als letztes eine Box der Sorte “E” aufgenommen hatten, können wir in dieser Reihe nicht mehr weitermachen und müssen eine weitere Box zurücklegen, bevor wir weitermachen.
  • Jedes Mal, wenn wir keine weitere Box mehr aufnehmen können, prüfen wir, ob die letzte zulässige Kombination mehr Sushi-Stücke enthält als die bisher ermittelte beste Kombination.

Wenn wir zum Beispiel 5 Boxen der Sorte “A” aufgenommen haben, können wir nicht mehr Boxen nehmen, da wir 15 € erreicht haben. Da wir die Boxensorten nach aufsteigendem Preis sortiert haben, macht es keinen Sinn, die letzte Box zurückzulegen und Boxen anderer Sorten zu probieren, da diese Kombinationen ja nur teurer sein können. Also legen wir die letzten beiden Boxen ab und nehmen als nächstes solange Boxen der Sorte “B” auf, bis wir die 15 € erreicht oder überschritten haben.

 

Diese Regeln beschreiben umgangssprachlich einen “Algorithmus”, also eine eindeutige Handlungsvorschrift zur Lösung des Problems, die zum Beispiel auch ein Computer umsetzen könnte. Der gesamte Ablauf ist im Folgenden grafisch dargestellt, wobei ein Pfeil nach rechts “aufnehmen” bedeutet, ein Pfeil nach links “zurücklegen” und neben den Boxen jeweils die Gesamtkosten und Gesamtstückzahl stehen, die man mit dieser Kombination erreicht hat. Rot dargestellt sind Kombinationen, die zu teuer für uns sind.

Ablauf

 

0€

0

->

A 3€

4 Stück

->

A 6€

8 Stück

->

A 9€

12 Stück

->

A 12€

16 Stück

->

A 15€

20 Stück

neue beste Lösung: A,A,A,A,A mit 20 Stück Sushi
              <-

A 12€

16 Stück

<-

A 15€

20 Stück

 

0€

0

->

A 3€

4 Stück

->

A 6€

8 Stück

->

A 9€

12 Stück

->

B 13€

17 Stück

->

B 17€

22 Stück

 
              <-

B 13€

17 Stück

<-

B 17€

22 Stück

0€

0

->

A 3€

4 Stück

->

A 6€

8 Stück

->

A 9€

12 Stück

->

C 15€

22 Stück

    neue beste Lösung: A,A,A,C mit 22 Stück Sushi
          <-

A 9€

12 Stück

<-

C 15 €

22 Stück

     

0€

0

->

A 3€

4 Stück

->

A 6€

8 Stück

->

B 10€

13 Stück

->

B 14€

18 Stück

->

B 18€

23 Stück

 
              <-

B 14€

18 Stück

<-

B 18€

23 Stück

 

0€

0

->

A 3€

4 Stück

->

A 6€

8 Stück

->

B 10€

13 Stück

->

C 16€

23 Stück

     
          <-

B 10€

13 Stück

<-

C 16€

23 Stück

     

0€

0

->

A 3€

4 Stück

->

A 6€

8 Stück

->

C 12€

18 Stück

->

C 18€

28 Stück

     
          <-

C 12€

18 Stück

<-

C 18€

28 Stück

     

0€

0

->

A 3€

4 Stück

->

A 6€

8 Stück

->

D 15€

21 Stück

         
      <-

A 6€

8 Stück

<-

D 15€

21 Stück

         

0€

0

->

A 3€

4 Stück

->

B 7€

9 Stück

->

B 11€

14 Stück

->

B 15€

19 Stück

     
          <-

B 11€

14 Stück

<-

B 15€

19 Stück

     

0€

0

->

A  3€

4 Stück

->

B 7€

9 Stück

->

C 13€

19 Stück

->

C 19€

29 Stück

     
          <-

C 13€

19 Stück

<-

C 19€

29 Stück

     

0€

0

->

A  3€

4 Stück

->

B 7€

9 Stück

->

D 16€

22 Stück

         
      <-

B 7€

9 Stück

<-

D 16€

22 Stück

         

0€

0

->

A 3€

4 Stück

->

C 9€

14 Stück

->

C 15€

24 Stück

        neue beste Lösung: A, C, C mit 24 Stück Sushi
      <-

C 9€

14 Stück

<-

C 15€

24Stück

         

0€

0

->

A 3€

4 Stück

->

D 12€

17 Stück

->

D 21€

30 Stück

         
      <-

D 12€

17 Stück

<-

D 21€

30 Stück

         

0€

0

->

A 3€

4 Stück

->

E 13€

22 Stück

->

E 23€

40 Stück

         
  <-

A 3€

4 Stücl

<-

E 13€

22 Stück

<-

E 23€

40 Stück

         

0€

0

->

B 4€

5 Stück

->

B 8€

10 Stück

->

B 12€

15 Stück

->

B 16€

20 Stück

     
          <-

B 12€

15 Stück

<-

B 16€

20 Stück

     

0€

0

->

B 4€

5 Stück

->

B 8€

10 Stück

->

C 14€

20 Stück

->

C 18€

25 Stück

     
          <-

C 14€

20 Stück

<-

C 18€

25 Stück

     

0€

0

->

B 4€

5 Stück

->

B 8€

10 Stück

->

D 17€

23 Stück

         
      <-

B 8€

10 Stück

<-

D 17€

23 Stück

         

0€

0

->

B 4€

5 Stück

->

C 10€

15 Stück

->

C 16€

25

Stück

 

 

     
      <-

C 10€

15 Stück

<-

C 16€

25 Stück

         

0€

0

->

B 4€

5 Stück

->

D 13€

18 Stück

->

D 22€

31 Stück

         
      <-

D 13€

18 Stück

<-

D 22€

31 Stück

         

0€

0

->

B 4€

5 Stück

->

E 14€

23 Stück

->

E 24€

41 Stück

         
  <-

B 4€

5 Stück

<-

E 14€

23 Stück

<-

E 24€

41 Stück

         

0€

0

->

C 6€

10 Stück

->

C 12€

20 Stück

->

C 18€

30 Stück

         
      <-

C 12€

20 Stück

<-

C 18€

30 Stück

         

0€

0

->

C 6€

10 Stück

->

D 15€

23 Stück

->

D 24€

36 Stück

         
      <-

D 24€

36 Stück

<-

D 24€

36 Stück

         

0€

0

->

C 6€

10 Stück

->

E 16€

28 Stück

             
  <-

C 6€

10 Stück

<-

E 16€

28 Stück

             

0€

0

->

D 9€

13 Stück

->

D 18€

26 Stück

             
  <-

D 9€

13 Stück

<-

D 18€

26 Stück

             

0€

0

->

E 10€

18 Stück

->

E 20€

36 Stück

             

0€

0

<-

E 10€

18 Stück

<-

E 20€

36 Stück

            fertig, beste gefundene Lösung: A,C,C mit 24 Stück Sushi

 

Damit haben wir alle Kombinationen, die wir mit 15 € kaufen können, ohne unnötig Geld übrig zu behalten, ausprobiert und dabei die für uns beste Option ermittelt: Wir können maximal 24 Stück Sushi kaufen, indem wir 1x Box A mit 4 Stück für 3 € und 2x Box C mit je 10 Stück für 6 € kaufen.

 

Die Anzahl der Kombinationen, die man bei einem Rucksackproblem testen muss, kann allerdings sehr groß werden, was dieses Problem in der Praxis zu einer harten Nuss macht: Angenommen, wir können eine Auswahl aus n verschiedenen Objekten treffen, um unseren Rucksack zu packen, dann sind im Zweifelsfall 2n Kombinationen möglich, die überprüft werden müssen! Das wären zum Beispiel bei 20 verschiedenen Objekten 220 = 1048576, also über eine Million mögliche Kombinationen – und in realistischen Anwendungsfällen rechnet man in der Regel mit deutlich größeren Zahlen!

Lösung mit Dynamischer Programmierung

Eine elegante Lösung stellt die sogenannte “Dynamische Programmierung” dar. Diese Methode basiert darauf, die Lösung des Gesamtproblems schrittweise aus Lösungen von kleineren Teilproblemen zusammenzusetzen. In diesem Fall reduzieren wir in einem solchen Teilproblem die Kostenschranke und die erlaubten Objekte.

Sehen wir uns erst einmal ein konkretes Beispiel für ein solches Teilproblem an, nämlich die Frage, wie man nur mit Boxen der Sorten “A” und “B” bei einer Kostenschranke von 8 € eine optimale Kombination findet.

Nehmen wir an, dass wir für die Kostenschranken 1 € bis 8 € die optimale Kombinationen, die nur aus “A”-Boxen besteht, bereits kennen. Nun möchten wir wissen, wie man für die Kostenschranke 8 € die optimale Kombination findet, in der man auch “B”-Boxen nehmen darf. Im Wesentlichen gibt es hier drei Fälle:

  • Wir nehmen gar keine “B”-Box. Dann benutzt die optimale Kombination nur “A”-Boxen und diesen Wert kennen wir bereits.
  • Wir nehmen genau eine “B”-Box. Dann benutzt die optimale Kombination also “A”-Boxen im Wert von 4 €, da wir von unserer Kostenschranke von 8 € die Kosten von 4 € für eine “B”-Box abziehen müssen.
  • Wir nehmen genau zwei “B”-Boxen. Dann benutzt die optimale Kombination keine “A”-Boxen, da wir die 8 € bereits vollständig verbraucht haben.

 

Mit Hilfe dieser Idee kann man nun eine Lösungsstrategie entwerfen: In der ersten Runde berechnet man jeweils in 1-€-Schritten für Kostenschranken von 1 € bis 15 € die optimalen Kombinationen, wenn man nur Boxen der Sorte “A” wählen darf. In der nächsten Runde überprüft man dann für jede Kostenschranke, ob man eine bessere Kombination erhält, wenn man eine oder mehrere Boxen aus der vorigen Lösung durch eine Box der Sorte “B” ersetzt. So macht man dann drei Runden weiter, bis man auch “E” überprüft hat.

Diesen Algorithmus kann man folgendermaßen in einem “Pseudocode” beschreiben, also in einer anschaulichen und trotzdem formalen Sprache, die an höhere Programmiersprachen wie Java oder C++ angelehnt ist:

Eingabe:

  • Menge der Objektsorten {A, B, C, D, E}
  • Kostenschranke m = 15
  • Kostenfunktion K
  • Nutzenfunktion N

wobei K und N jeweils die Objektsorte auf den entsprechenden Kosten- oder Nutzenwert abbilden (z. B. K(A) = 3 und N(A) = 4, also 3 € Kosten und 5 Stück Sushi für Boxen der Sorte “A”).

Algorithmus:

Setze R(1) = 0, ..., R(m) = 0
Setze S(1) = 0, ..., S(m) = 0
Wiederhole für alle s in {A, B, C, D, E}:
{
  Wiederhole für alle k von K(s) bis m:
  {
    Setze r = R(k - K(s)) + N(s)
    Wenn R(k) < r, dann:
    {
      Setze R(k) = r
      Setze S(k) = s
    }
  }
}

Ausgabe:

Der Algorithmus berechnet in jedem Eintrag R(k) den optimalen Gesamtnutzen, den man mit Gesamtkosten ≤ k erreichen kann. In S(k) steht jeweils die Sorte des Objekts, das hierbei zuletzt in die Auswahl aufgenommen wurde.

Die Zwischenergebnisse für R und S nach jeder Runde sind in der folgenden Tabelle dargestellt:

  i = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
j = 1 R(i) = 0 0 4 4 4 8 8 8 12 12 12 16 16 16 20
  S(i) =     A A A A A A A A A A A A A
j = 2 R(i) = 0 0 4 5 5 8 9 10 12 13 14 16 17 18 20
  S(i) =     A B B A B B A B B A B B A
j = 3 R(i) = 0 0 4 5 5 10 10 10 14 15 15 20 20 20 24
  S(i) =     A B B C C B C C C C C C C
j = 4 R(i) = 0 0 4 5 5 10 10 10 14 15 15 20 20 20 24
  S(i) =     A B B C C B C C C C C C C
j = 5 R(i) = 0 0 4 5 5 10 10 10 14 18 18 20 22 23 24
  S(i) =     A B B C C B C E E C E E C

Der optimale Gesamtnutzen, den man mit Kosten von max. 15 € erreichen kann, steht hier am Ende also in R(15).

Wie bekommen wir jetzt aber die optimale Kombination heraus, mit der man diesen Gesamtnutzen erreichen kann? Dazu schauen wir in die Einträge von S aus der letzten Runde, um herauszufinden, welches Objekt jeweils zum Erreichen der besten Lösung hinzugefügt wurde:

  • Der optimale Wert R(15) = 24 wurde mit S(15) = C erreicht, also enthält unsere Auswahl eine Box der Sorte “C”.
  • Da die Kosten dieses Objekts K(C) = 6 betragen, müssen wir als nächstes bei S(15 – 6) nachschauen: Da S(9) = C ist, enthält die optimale Lösung eine weitere Box der Sorte “C”.
  • Jetzt prüfen wir noch S(9 – 6): Da S(3) = A ist, kommt noch eine Box der Sorte “A” hinzu.

 

  i = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
j = 5 R(i) = 0 0 4 5 5 10 10 10 14 18 18 20 22 23 24
  S(i) =     A C C

Damit sind wir fertig und erhalten auch hier als beste Kombination 1x Box “A” und 2x Box “C” mit insgesamt 24 Sushi-Stücken.

Wie man sieht, muss dieser Algorithmus maximal n x m Vergleiche durchführen, was in der Praxis (abhängig von den maximal erlaubten Kosten m) sehr viel schneller sein kann als die oben erwähnten 2n Vergleiche.