Knapsack-Problem

[kak]

Es geht um folgendes.... man hat einen Rucksack mit einer bestimmten Größe. dann hat man auch Goldstücke mit verschiedenen Größen bzw Gewicht. Jetzt soll man die maximale Belegung für den Rucksack rausfinden, welchle Goldstücke man einpacken darf.

z.B.

man hat 4 Goldstücke: Größe bzw. Gewicht von 4,5,7,1
der Rucksack ist von der Größe 10

also wäre es möglich das Goldstück 4,5,1 einzupacken und der Rucksack wäre optimal bepackt.

Jedes Goldstück ist natürlich mehrmals vorhanden...


Kann mir da jemand weiterhelfen wie ich das Array und die Funktion für das Maximale was man an Goldstücken mitnehmen darf, schreiben muß

Danke

[Diogenes]

Um erlich zu sein ;( da wirst Du etwas auf die Antwort warten müssen, denn das Problem ist keineswegs trivial. :mauer: Frust ist garantiert, wenn Du´s ausprobierst.

Außerdem ist das Problem keineswegs Pascal-spezifisch und wird deswegen ins "Algorithmen"-Forum verschoben. Dort findest Du hoffentlich mehr Hilfe.

[Diogenes]

Den Google ein bißchen stöbern zu lassen, zahlt sich aus:
Hier habe ich etwas gefunden, das vielleicht hilft. Ist zwar in C, aber immerhin... ;)

http://www.diku.dk/~pisinger/codes.html

[Chris Hunter]

Ich hab das Problem zwar verstanden. aber wozu ist es denn überhaupt zu gebrauchen? ich meine wo liegt denn da der verwendungszweck?!?

[Codeq]

och nu komm.... so fantasielos ?
stell dir vor du sollst nen programm schreiben das LKWs optimal bepackt mit waren die verschickt werden sollen....
ein beispiel... gibt glaube ich nocht ettliche mehr...

oder du willst musik auf ne 10CDs brennen und willst nun den platz der CD optimal ausnutzen mit den songs die du hast....


usw usw....

:mauer:

[Chris Hunter]

mmmmhh. ok