Guten Tag,
Ich habe mich hier angemeldet, da ich ziemlich verzweifelt bin. Hört ihr hier sicherlich öfters.

Wir haben die Aufgabe bekommen, eine Tabelle von 8 Gewichten und 8 Profiten jeweils mit dem Alogrhithmus des Rucksackproblems zu lösen.
Ich habe mir nun gedanken gemacht und bin bisher bis zu diesem Schritt gelangt, dass mein Programm alle Möglichkeiten in einer visuellen Canvas Funktion dargestellt werden kann. Das Problem darin besteht jedoch, dass nur die obersten Punkte von Relevanz sind und die anderen nichts mehr als Rechenleistung kosten.

Den Code kann ich bei bedarf gerne anknüpfen.

Ich habe mich auch belesen und bemerkt, dass dieses Problem mit Hilfe der Pareto Optimal Punkte gelöst werden kann. Nur fehlt mir der Ansatz, wie ich eine Liste mit N+1 Elementen in Delphi implementieren kann, wenn ich jedoch nur über 8 Erträge verfüge?

Da ist bei mir im Kopf ein ganz großer Denkfehler drin und ich weiß nicht, wie ich diesen beseitige und in Delphi implementieren kann.

Könnte mir jemand bei meinem Problem behilflich sein?
Danke im vorraus.
Gruß,
Itzehoh

edit: Achso, ich habe auch noch ein Problem mit der Canvas Darstellung.
Immer, wenn ich die Punkte berechne, sprengt die Funktion jeglichen Rahmen meines Bildschirmes. Kann ich die Funktion irgendwie Miniaturgetreu verkleinern, so dass sie in ein vorgezeichnetes Koordinatensystem eingefügt werden kann?

Moderiert von Narses: Überflüssige Zeilenumbrüche/Leerzeilen entfernt.

Hi,

eine Liste mit N Elementen wird dir dabei nicht so richtig viel helfen.

Bei 8 Gegenständen hast du 2^8 = 256 Möglichkeiten, den Rucksack zu befüllen, wie du ja aber schon schreibst, sind in den meisten Fällen viele dieser Möglichkeiten absehbar schlecht, und können deshalb früh verworfen werden.

Hast du schon eine Idee, wie man da rangehen kann?

Eine Inspirationsquelle könnte evtl. www-i1.informatik.rw...gorithmus/algo15.php hier zu finden sein

Nein, leider nicht, mein Kopf stellt sich in dieser Problematik quer...
Der Link war bisher meine Hauptinspirationsquelle, habe das programm nach dem Prinzip erstellt.
Nun muss die Funktion integriert werden, um von den 256 Möglichkeiten die 16 besten Punkte zu erfahren.
Nur hilft mir die Seite da auch nicht mehr weiter. Leider.

Ich könnte dir noch einen anderen Algorithmus anbieten, der das Rucksackproblem auch löst:

Du schreibst eine Funktion optimal(groeße:integer; gegenstaende:integer) die folgendes leisten soll:
optimal(s,g) löst das Rucksackproblem für einen Rucksack der Größe s mit den ersten g Gegenständen aus deiner Liste.

Implementieren lässt sie sich dann so:

optimal(0,g) = 0
optimal(s,1) = Profit von Gegenstand 1, wenn Gewicht Gegenstand 1 < s sonst 0
optimal(s,g) = Maximum aus optimal(s,g-1) (= der g-te Gegenstand kommt nicht in den Rucksack) und optimal(s - Gewicht Gegenstand g, g-1) (= der g-te Gegenstand kommt in den Rucksack). Ist das Gewicht des g-ten Gegenstandes größer als s wird natürlich optimal(s,g-1) zurückgegeben.


Damit der Algorithmus sich nicht in andauernden Neuberechnungen derselben Werte verzettelt, lassen sich diese in einem 2-dimensionalem Array speichern.

@jann1k: Das ist ja der Ansatz von Ibarra und Kim, auch wenn der asymptotisch die selbe Laufzeit hat, ist er praktisch doch deutlich schlechter...

WENN man sich tiefergehend damit beschäftigen will, ist das Paper von Lawler (Fast approximation algorithms for knapsack problems) zu empfehlen, aber ich glaube, das geht hier zu weit.

@Itzehoh: Du kannst die Teilmengen, die du erstellt hast, ja aufsteigend nach ihrem Gewicht sortieren. Dann gehst du die Liste durch, und guckst, welche Items die Optimalitätsbedingungen erfüllen...


edit:

Itzehoh hat folgendes geschrieben :

Nun muss die Funktion integriert werden, um von den 256 Möglichkeiten die 16 besten Punkte zu erfahren. Nur hilft mir die Seite da auch nicht mehr weiter. Leider.

Weißt du, dass es in deinem Beispiel 16 beste Punkte gibt?
Es kann auch vorkommen, dass alle Punkte optimal sind, z.B. wenn das Gewicht jedes Items genau seinem Profit entspricht.

Nach dem Prinzip auf der Seite sind die Optimalpunkte ja diese, die keinen weiteren Punkt mehr links oberhalb von diesem haben.
Das sind bei mir (ich darf mir die Werte aussuchen, deswegen alles unterschiedliche, die Problematik mit den gleichen Werten ist mir bewusst, das gehört aber nicht zu meinem Aufgabenbereich) eben bei 256 Möglichkeiten diese 16 Punkte. Der Rest ist nebensächlich und kann gelöscht werden. Es gibt also 16 Punkte, die keinen besseren Profit für die Möglichkeit haben.
Nur diese Punkte brauch ich ja.
Wie bringe ich Delphi bei, genau diese Punkte zu ermitteln? Habe gedacht, über die Position der Canvas Funktion, da diese aber dynamisch ist, kann Delphi dort ja aber keine genauen Grenzen ermitteln, oder?
Die Seite besagt ja, dass von einem Punkt (0;0) ausgegangen wird unr dann mit i+1 bis N wiederholt werden. Was ist in diesem Fall aber i? Das gewicht, der Profit, oder die Kombination?

@ Thorsten: Ich habe alle Punkte in einer Paintbox dargestellt, könnte diese notfalls also ablesen. Sortieren finde ich daher eher unnötig, oder wie meinst du das?

@ Yannik: Die Methode von dir berechnet jetzt aber alle Möglichkeiten, die ein gewisses Gewicht x nicht übersteigen?
Das habe ich bereits gelöst, jedoch habe ich bewusst alle Möglichkeiten anzeigen lassen, um einen besseren Überblick zu schaffen. Über eine feste Funktion einer Trennlinie habe ich die Gewichtsgrenze dargestellt.


Theorethisch muss ich Delphi ja nur sagen, dass er die 16 höchsten Werte ausliest und einzeln angibt. Aber wie?

Wenn du mehrere "Punkte" (also Teilmengen) hast, die das gleiche Gewicht haben, kannst du ja diejenige mit dem höheren Profit nehmen.

Wenn die Teilmengen aufsteigend nach Gewicht sortiert sind, kannst du ja die Liste durchgucken. Die erste Teilmenge (mit Gewicht 0) erfüllt die Optimalitätsbedingung, die nächste auch, sofern du keine Gegenstände mit Profit oder Gewicht 0 hast. Jetzt kannst du die Liste durchgehen, und solange Teilmengen rausschmeißen, bis du eine gefunden hast, die mehr Profit als die nächste bringt. Diese nimmst du auch auf, und guckst von da aus wieder weiter, welche Teilmengen nicht mehr Profit bringen, und schmeißt die wieder raus.

Das solltest du aber in der Logik machen, und von der graphischen Darstellung trennen.

Ich hab jetzt alles in einer Stringgrid Tabelle angegeben.
Da ich absolut nicht weiter weiß, versuche ich nun einfach über zweimaliges sortieren
herauszubekommen, welche Kombination die besten sind.