Rekursives Verfahren zur Lösung des Rucksackproblems

hi karlcash.

erstmal ohne den algorithmus: konstruktion der lösung folgendermaßen:
du hast zwei matrizen, in der wegematrix liest du jetzt die lösung ab, indem du beim letzten wert (letzte zeile, letzte spalte) beginnst. am beispiel im skript (s. 73) ist das 4.
also: wenn du 10 kapazitätseinheiten hast (zeile "10") und alle 5 güter zur verfügung stehen, packst du gut 4 definitiv einmal ein. gut 4 benötigt 2 kapazitätseinheiten (koeffizient in der nebenbedingung), daher schaust du als nächstes, was bei 8 kapazitätseinheiten zusätzlich eingepackt werden soll (wieder in der letzten spalte gucken, da ja alle güter x1-x5 zur verfügung stehen); wieder eine 4; wieder 2 kapazitätseinheiten weniger; also als nächstes bei zeile 6 schauen. dann kommt zeile 4, dann zeile 2 und letztendlich ist der rucksack voll und du hast 5 stück von gut 4 eingepackt und nichts von den anderen.

der algorithmus ab punkt 6:
6) packe ein gut xj in den rucksack; welches xj? j ist abzulesen in der wegematrix für (n,b), zu beginn also für n=5 und b=10. hier also einmal gut 4 einpacken.
7) veringer die kapazität b um diejenige, die das gerade dazugepackte gut einnimmt; aj(n,b): koeffizient aus der nebenbedingung vor dem xj, was man eingepackt hat, hier also von x4: 2, das neue b ist 10-2=8
8) solange noch kapazität über 0 ist, wieder zu 6)
-> nächstes xj: j ablesen in wegematrix für j(n,b); diesmal ist b in 7) verringert worden! n=5 bleibt bestehen. also die letzte spalte (spalte n=5) in der wegematrix "hochwandern" (die kapazitäten hochwandern, b verringert sich ja mit jedem dazugepackten stück)
usw. bis man fertig ist 😉

hoffe, das hat schon ein wenig geholfen? ich hab die klausur im märz geschrieben und bin vielleicht schon wieder ein wenig raus, was das "verständliche erklären" angeht

auch hier. Vielen vielen Dank. Was schreibst du denn noch?

Gruß

karlcash

karlcash schrieb:

Was schreibst du denn noch?

Zum Vergrößern anklicken....

...den antrag auf austellung des diploms 😀 - wenn dann iiiiiirgendwann mal die noten raus sind. hatte noch zwei weitere OR fächer (graphen und PMM) am gleichen tag geschrieben, und bei allen stehen die noten noch aus (dienstag sinds 8 wochen...). solang halt ich die grauen zellen bisschen wach und gucke, obs hier fragen gibt, die noch keiner beantwortet hat