Die häufigsten dyn. Prog. Anwendungsmöglichkeiten habe ich eher in Graphentheorie gesehen (Rucksackproblem kann auch darauf abgebildet werden). Was aber der Anschaulichkeit für "nicht-Nerdler" doch eher abträglich ist
. Rucksackproblem ist daher schon mal nicht schlecht.
Zu Deinem Algo:
Was ist z.B. beim Rucksackproblem so schlecht an dem Algorithmus:
- Berechne für jeden Gegenstand das Wert/Gewichts-Verhältnis
- Sortiere die Gegenstände nach diesem Verhältnis
- Nehme den jeweils obersten Gegenstand der Liste bis der nächste Gegenstand nicht mehr in den Rucksack passt.
- Überspringe diesen Gegenstand, nehme den nächstbesten der passt
- Wiederhole so lange bis entweder der Rucksack voll ist oder keine Gegenstände mehr da sind.
Gegenbeispiel: bei einem Gewinnspiel "ein Karton vom Laster" hat man folgende Geräte zur Auswahl:
Asis Netbook: 1kg, 600 Euro, W/G = 600
Leenovo Thunkpad: 2kg, 1000 Euro, W/G=500
Birne MucBack Pro: 3kg, 1200 Euro, W/G = 400
Und eine Mini-Frauenhandtasche, die nur 5kg tragen kann(daher auch Mini
).
Nach Deinem Algo:
600,500,400:
liefert:
Asis Netbook und Leenovo Thunkpad mit einem Gesamtwert von 1600 Euro
Optimal:
Leenovo und Birne MucBack Pro: 2200 Euro
;----------------------
Greedy findet nur ein lokales Optimum. Anders gesagt: man findet (recht schnell) eine Lösung, weiß aber nicht, wie gut diese ist.
Um optimale Lösung zu finden, muss man alle Lösungsmöglichkeiten betrachten. Und hier gibt es den Unterschied zwischen "dynamisch" und "naiv/normal/rekursiv/backtracking".
Naive Lösung:
Bilde Kombinationen und merke die beste.
Code:
<typischer Backtrackingalgo für Rucksackproblem einsetz>
oder:
Nehme Gegenstand1, packe in den Rucksack
Nehme Gegenstand2 ... bis Rucksack voll.
Merke Lösung
Packe letzten Gegenstand aus,packe einen anderen rein
Merke Lösung, falls besser als letzte
Packe letzen Gegenstand aus ... bis alle durchprobiert wurden
Packe die beiden letzen Gegenstände aus, packe nun einen anderen Gegenstand ein (usw, bis man wieder beim leeren Rucksack angekommen ist und nun mit
"Nehme Gegenstand2, packe diesen in den Rucksack" anfängt).
Graphisch schaut das so aus:
Code:
_+G1_________{}________+G4
___-{G1} | | \.\ \
+G2 / +G2| \... ... ... ... {G4}
/ | /||||\ +G1
{G1,G2} {G1,G3} .......{G4,G1}
+G3 / | \ \ / | /|||||\ + G2
/ |+G4 \ ..... | +G2 ....... {G4,G1,G2}
G1,G2,G3} | \ {G1,G3,G2}
{G1,G2,G4} ...
"..." sind weggelassene Abzweigungen.
Wie man unschwer erkennen kann, werden hierbei oft gleiche Lösungen mehrfach generiert/betrachtet (die Gegenstände kommen in einer anderen Reihenfolge in den Rucksack).
{G1,G2,G3} == {G1,G3,G2} == {G2,G3,G1}
Laufzeit: Pi *Daumen * (Gesamtanzahl der Gegenstände ^ (max. Pfadtiefe bzw. Gegenstände, die das max. Gewicht erreichen)).
Also Exponentiell.
Edit:
Eigentlich würde ja ausreichen, nur einen kleinen Teil der möglichen Pfade zu verfolgen - der Rest ist "dasselbe in grün/blau/rot".
Da müsste man aber immer noch alle Kombinationen bis zum zulässigen Gewicht ausrechnen, was imho in die Richtung von Binomialkoeffizint
("Gesamt_gegenstände" über "max. anzahl die in den Rucksack passt") oder wie beim Lotto: (bei 50 Gegenständen) "x aus 50".
/Edit
Prinzipiell spricht nichts dagegen, den naiven Backtracking Algoritmus mit einer Datenbank auszustatten, die bereits berechnete Ergebnisse speichert. Wichtig wäre nur, dass die Reihenfolge der Gegenstände nicht beachtet wird (also einfach ein Set). Auf "neuprogrammisch" kann man auch vom "memoizing" des Algos sprechen.
Dynamische Programmierung:
[OT]
Der "i+j" Algo"kram" aus Wikipedia ist ein Tribut an die uncoolen Zeiten, als der Speicher noch rar und teuer war und die Algos auf die Lochkarten gestanzt werden mussten * :evil: * [/OT]
Ernsthaft: während bei der "naiven" Methode man "von oben nach unten" geht, berechnet man bei dynamischer Programmierung Teillösungen und setzt diese zu einer Lösung zusammen.
Code:
wikipedia:
Eingabe: U = 1..n Gegenstände, B(ound), w(eight), v(alue) [FONT=monospace]
[/FONT]R := [1…(n+1), 0…B]-Matrix, mit Einträgen 0
FOR i = n … 1
FOR j = 1 … B
IF w(i) <= j[FONT=verdana]
[/FONT]R[i,j] := max( v(i) + R[i+1, j-w(i)], R[i+1,j] )[FONT=monospace]
[/FONT]ELSE[FONT=verdana]
[/FONT]R[i,j] := R[i+1,j][FONT=verdana]
[/FONT]Ausgabe: R[1,B]
1 to n sind Items. Wie man sieht, wird die Liste nur 1 mal durchlaufen.
0 to W sind ganzzahlige Gewichte. Wenn also 50kg das Maximum sind:
1,2,3 ... 49,50
Anders gesagt: für jeden Gegenstand 1..n werden die möglichen Gewichte betrachtet und nach maximalen Nutzwert ausschau gehalten:
Code:
Gew/Gegenstand:
3 2 1
1 0 0 0
2 0 0 0
3 0 0 0
Code:
[/FONT][FONT=monospace]
[/FONT]R := [1…(n+1), 0…Max_gewicht]-Matrix, mit Einträgen 0
FOR Gegenstand aus Liste:
FOR kg = 1 … Max_gewicht
IF Gewicht(Gegenstand) <= kg[FONT=verdana]
[/FONT]R[Gegenstand,kg] := max(Preis(Gegenstand) + R[vorheriger_gegenstand, kg-Gewicht(Gegenstand)], R[vorheriger_gegenstand,kg] )[FONT=monospace]
[/FONT]ELSE[FONT=verdana]
[/FONT]R[Gegenstand,kg] := R[vorhergiger_gegenstand,kg][FONT=verdana]
[/FONT]Ausgabe: R[letzter_gegenstand,Max_gewicht]
Die Lösung ergibt sich also aus den vorberechneten Teillösungen (z.B Eintrag für alle Gewichte des vorherigen Gegenstands)
vielleicht ist das hier etwas anschaulicher: http://polya.computing.dcu.ie/courses/ca313/w6/index.html![[HaBo]](/styles/default/logoklein.png){kind=small}
[0]
