Rucksackproblem

[KeinePanik92]

ich muss in informatik eine hausarbeit in delphi schreiben. leider ist mein lehrer total unfähig und ich hab keine ahnung wie ich das machen soll. das problem:
Gegeben ist ein Rucksack mit einer maximalen Tragfähigkeit G und n Gegenständen unterschiedlichen Gewichts und unterschiedlichen Wertes. Der Rucksack soll so mit den Gegenständen bepackt werden, dass einerseits das Gesamtgewicht der eingepackten Gegenstände die Tragfähigkeit des Rucksacks nicht überschreiten und andererseits der Gesamtwert möglichst groß wird.


So, vielleicht könnt ihr mir das programmieren. Auf jedenfall schonmal danke im voraus.

[Dr.No]

Interessantes Problem. Da hat Euch Euer Lehrer doch bestimmt noch mehr Informationen gegeben, oder ? Oder hast Du da gerade gepennt ?

Ich vermute, Ihr sollt eine Näherungslösung ermitteln. Ist dem so ? Hat er gesagt. mit welchem Algorithmus ?

Eine exakte Lösungsberechnung würde IMHO den Rahmen einer Hausaufgabe sprengen. Dass eine solche Berechnung nicht so ohne ist, erkennt man schon daran, dass das Rucksackproblem eines der berühmtesten Probleme der Operations Research ist.

[KeinePanik92]

nö, warum sollte er uns mehr infos gegeben haben. ich hab doch gesagt, er ist total unfähig. er hat uns einfach ein blatt mit dieser aufgabe drauf gegeben und hat gesagt, so macht mal. wieso, braucht man denn mehr informationen?
na, der algorithmus soll in delphi geschrieben werden.
ich hab einfach keine ahnung davon.

[Dr.No]

Euer Lehrer ist wirklich ein Trottel. Das Rucksackproblem gehört zu einem der schwierigsten Probleme der Optimierung. Da kann man nicht einfach sagen "mach mal".

Ich versuche mal, obwohl ich eigentlich keine Zeit habe,einen Lösungsweg darzustellen, der zwar relativ einfach, jedoch nur für eine kleinere Anzahl von Gegenständen brauchbar ist ( 30 Stück wäre schon ein Härtefall ), einfach deshalb, weil die Rechenzeit mit der Anzahl rapide anwächst. Aber alles andere würde den Rahmen dieses Forums weit sprengen.

Die Idee ist, alle möglichen Kombinationen der Bepackung durchrechnen. Für jede Kombination wird das Gewicht und der Wert bestimmt. Falls das Gewicht größer ist als die max. Tragfähigkeit, wird die Kombination als unzulässig verworfen. Von den zulässigen Kombinationen ist diejenige, die den maximalen Wert ergibt, die Lösung. Das Verfahren ist auch unter dem Stichwort "Enumeration" bekannt.

G = maximale Tragfähigkeit
N = Anzahl der Gegenstände
k = lfd. Nr. der Kombination
i = lfd. Nr. des Gegenstandes
V[i] = Wert des Gegenstandes i
W[i] = Gewicht des Gegenstandes i
WK = Gewicht der Kombination
VK = Wert der Kombination

AW[i] = Auswahl des Gegenstandes i

Der Auswahlvektor AW beschreibt, welcher Gegenstand eingepackt wird (siehe Beispiel)
0 --> wird nicht eingepackt
1 --> wird eingepackt

Beispiel:
N = 3, es gibt 2**3 = 8 Kombinationen (** bedeutet hoch)

Kombination Auswahlvektor AW
k G2 G1 G0
---------------------------
0 0 0 0
1 0 0 1
2 0 1 0
3 0 1 1
4 1 0 0
5 1 0 1
6 1 1 0
7 1 1 1

bei der Kombination Nr. 5 werden also die Gegenstände G0 und G2 eingepackt

Der Algorithmus wäre also etwa so:

VMax = 0 // maximaler Wert
kMax = -1 // Kombination, die den maximalen Wert ergibt

Für k = 0 .... 2**N - 1
{
Bestimme den Auswahlvektor AW für diese Kombination
Rechne das Gewicht der Kombination WK = AW[0] * W[0] + AW[1] * W[1] + AW[2] * W[2]
Wenn (W > G) --> weiter mit nächster Kombination
Rechne den Wert der Kombination VK = AW[0] * V[0] + AW[1] * V[1] + AW[2] * V[2]

Wenn (VK > VMax)
{
VMax = VK;
kMax = k;
}
}

Schon sind wir fertig, die Kombination kMax liefert den maximalen Gesamtwert VMax

Die Bestimmung des Auswahlvektors ist das einzige Problem hier.

Am Beispiel der Kombination 5:

Jede Zahl wird, wie Du sicher weißt, durch ein Bitmuster repräsentiert.

1 0 1 -> 2**2 + 2**0 = 5.

Für i = 0 ... N-1
{
AW[i] = 1, wenn das i. Bit ( von rechts nach links gezählt!) der Variablen k gesetzt ist
sonst = 0
}

Bei der Zahl 5 ist das 0. und 2. Bit gesetzt, also setzen wir den 0. und 2. Wert von AW auf 1 ( wieder von rechts nach links gezählt ) --> AW = {1,0,1}

Wie Du in Delphi feststellen kannst, ob das entsprechende Bit gesetzt ist, kann ich Dir leider nicht sagen, da ich kein Delphi kann. Wenn Du es nicht weißt und eine gezielte Frage dazu hier stellst, wird Dir sicher jemand antworten.

Damit solltest Du alles wissen, um das Programm schreiben zu können. Wenn Dir jemand anderer ein Programm schreibt, das Du dann nicht verstehst, hast Du überhaupt nichts davon. Und Du willst doch programmieren lernen, oder ?

Noch zu Deiner Frage, ob man mehr Informationen braucht: In der Praxis wird man, abhängig von der max. möglichen Anzahl der Gegenstände, einen entsprechenden Algorithmus wählen. 5 Gegenstände wird man anders programmieren als 500. Und für dieses Problem gibt es viele Lösungsmethoden. Da muss ein guter Lehrer schon sagen, welchen man wählen soll. Manche Lösungsmethoden liefern auch nur Näherungslösungen. Deshalb muss er auch sagen, ob eine Näherungslösung genügt oder ob er eine möglichst exakte will, die dann natürlich einen höheren Programmieraufwand erfodert.

Die oben beschriebene liefert eine exakte. Das Verfahren ist allerdings für größere Mengen von Gegenständen nicht sehr effizient und bei mehr als vielleicht 30 Gegenständen unbrauchbar.

Viel Erfolg und auch etwas Spaß wünscht
Dr. No

[Soeren175]

Schade das er sich KEINEPANIK92 nicht mehr meldet, scheint wohl doch gepennt z u haben und hat nix kapiert.

Dr.No hat sich viel Mühe gemacht und ich fand es sehr interessant

lg

[Dr.No]

Danke Soeren175 für die aufmunternden Worte.

Warum eine solche Hilfestellung KeinePanik92 nicht mal eine Antwort, geschweige denn einen Dank wert ist, verstehe wer will, ich jedenfalls nicht.

Nur mal so zur Erinnerung an alle, die die Hilfen hier für das Selbstverständlichste auf der Welt halten: Diejenigen, die antworten, opfern dafür ihre Freizeit.

Grüße,
Dr. No