Rucksackproblem

[buff222]

Hallo zusammen,
ich habe ein kleines Problem mit einem Schulprojekt.
Ich soll das Rucksackproblem programmieren. Das Grundprinzip vom Rucksackproblem kenn ich, hab aber keine Ahnung wie ich das Rucksackproblem in Delphi umsetzen kann. :?
Die Vorgaben wieviel kilo getragen werden Können, wie schwer und welchen Wert die Objekte haben können auch im programm vorgegeben werden, falls es die Sache einfacher macht.

Ich brauche ganz dringend Hilfe bei der Programmierung, da ich das allein nicht hinkriege und mein Lehrer mir auch nicht gerade weiterhilft. Kleine Tipps könnten auch Hilfreich sein.

Ich bedank mich schonmal für eure Antworten :-D

[dino]

was ist denn das RucksackProblem???

[Luckie]

Hast du Problme beim Code oder schon beim Konzept? Wenn bei ersteren poste bitte deine konkrte Frage / problem zum Quellcode. Hast du Problem emit dem Konzept, wäre es sehr hilfreich, wenn du uns sagst, wie weit du schon bist und wo du jetzt Probleme hsst.

Aber im Moment kann man dir so keine Hilfe geben, weil du uns nicht sagst wo konkret du Probleme hast.

[freak4fun]

Zitat:

Zitat von dino

was ist denn das RucksackProblem???

Man sollte Antworten posten und nicht Fragen. :stupid: Rucksackproblem :roll:

MfG
freak

[dino]

man sollte das schon als Fragensteller dazuposten...

um welche gewichte handelt es sich und wieviel sind sie wert?

[Luckie]

Zitat:

Zitat von dino

um welche gewichte handelt es sich und wieviel sind sie wert?

Absolut irrelevant die Frage.

Man könnte einfach einen BruteForce Algorithmus auf das Problem los lassen und alle Möglichkeiten durchprobieren. Wäre natürlich so ziemlich das uneleganteste was es gibt, dafür aber ziemlich sicher und robust. ;)

[buff222]

Ich hätte gern einen ganzen Quellcode :D , wenns möglich wäre.
Konzept: Das tragbare Gewicht, die Gewichte der Objekte und dessen Wert sind vorgegeben und stehen noch auf der Form. Ein button zum ak#tivieren und ein Editfeld zur ausgabe...

danke für die schnellen antworten!!!

[Luckie]

Zitat:

Zitat von buff222

Ich hätte gern einen ganzen Quellcode :D , wenns möglich wäre.

Hier wird dir niemand deine Hausaufgaben machen. bei konkretne Problemen / Fragen helfen wir dir gerne, aber so nicht.

[Gausi]

Zitat:

Zitat von Luckie

Man könnte einfach einen BruteForce Algorithmus auf das Problem los lassen und alle Möglichkeiten durchprobieren. Wäre natürlich so ziemlich das uneleganteste was es gibt, dafür aber ziemlich sicher und robust. ;)

Da das Rucksackproblem NP-vollständig ist, bleibt einem nicht wirklich was anderes übrig, wenn man die exakte Lösung haben will. :stupid: (Ich gehe davon aus, dass bei "alle Möglichkeiten durchprobieren" schon gewisse Abbruchkriterein dabei sind, sodass nicht mehr dazu gepackt wird, wenn der Rucksack eh schon zu schwer ist.)

Man könnte zwar mit diversen Heuristiken rangehen, die evtl. eine Lösung finden, die (beweisbar) nur um einen gewissen Prozentsatz von der richtigen Lösung abweicht, aber das ist hier sicherlich nicht verlangt.

[Phoenix]

Naja. Es gibt da schon Ansätze.

z.B. Packt man ihn erstmal voll. Dann schaut man nach, ob man ein Paket durch ein/zwei/drei... leichtere, die einen höheren Nutzwert haben ersetzen lassen. Aus allen Möglichkeiten nimmt man die mit dem kleinsten Gewicht und dem höchsten Nutzwert aus. Ist Platz für ein neues Paket frei geworden nimmt man das mit dem höchsten Nutzwert das reinpasst. Das ganze so lange, bis nichts mehr geht.

Wenn das nicht mehr geht schaut man, ob sich dann zwei beliebige Pakete durch zwei/drei/vier... leichtere mit höherem Nutzwert ersetzen lassen. Gleiches Prozedere wie oben. Dann mit drei... vier... bis man nichts mehr tauschen kann.

Ist ein zielstrebigeres ausprobieren wobei man viele falsche Lösungen von vorneherein gar nicht probiert bzw. gleich wieder vwerwirft.

[dino]

ich habe erst alle 2hoch*anzahl an waren* Möglichkeiten erstellt für jedes Wert und kg gespeichert, alle werte genullt, wo kg überschritten ist und das anzeigen lassen, was den höchsten wert hat

[ste_ett]

Man könnte sich im Vorfeld eine Liste erstellen, in der jedes Element, das man in den Rucksack legen kann, einen bestimmten Wert, den man aus dem Verhältnis vom Preis zum Gewicht berechnet, zuordnet.
Je höher/niedriger (je nach Rechenart) der Wert, desto weiter vorne/hinten erscheint dieser Gegenstand in einer sortierten Liste.

Anhand der Liste füllst du den Rucksack erstmal mit den Gegenständen, bis entweder der Rucksack voll ist oder alle Gegenstände im Rucksack liegen.

Dann versuchst du, wie oben schon beschrieben, Gegstände zu tauschen.

[buff222]

Zitat:

Zitat von Luckie

Zitat:

Zitat von buff222

Ich hätte gern einen ganzen Quellcode :D , wenns möglich wäre.

Hier wird dir niemand deine Hausaufgaben machen. bei konkretne Problemen / Fragen helfen wir dir gerne, aber so nicht.

Ein Versuch wars wert :) ...

Danke schonmal für die vielen Antworten... :thumb:
Ich werd die Ansätze mal versuchen umzusetzen.
Was ich brauche ist also ein Sortieralgorithmus, mit dem ich sagen wir mal die Quotienten aus Gewicht und Wert sortiere und dann die kleinsten Quotienten zuerst in den Rucksack packe bis das gewicht die maximale Traglast überschreitet und kein Objekt mehr reinpasst.
Falls der Rucksack nicht komplett ausgefüllt wurde werden die letzten sachen die reingsteckt wurden mit den übrigen ausgetauscht, somit werden dann mehrere Möglichkeiten durchgespielt. Bis der höchste Wert gefunden wurde.

Mal grob zusammengafasst, dass ich das auch richtig verstanden habe.
Verbessert mich wenn ich irgendwo falsch liege.

Geb mich jetz mal dran, wenn ich fragen zum Quellcode habe, kann ich mich doch sicher an euch wenden. :wink:

Danke nochmals

[alzaimar]

Beim 0/1-Knapsack-Problem gibt es keine richtige Strategie. Brute-Force und Backtracking ist das einzige Verfahren, das die optimale Ergebnis liefert.

Die 'Chaos'-Suche (evoutionäre Programmierung) ist aber schon lustig:

Code:

1. Finde eine (suboptimale) Lösung (Rucksack ist  voll)
2. Nimm ein paar Dinge raus und pack ein paar wieder rein.
3. Wenn der Rucksack nun besser gepackt ist, fein. Dann haben wir eine neue (suboptimale) Lösung
4. Goto 2

Das Schöne ist, ich kann jederzeit abbrechen und habe eine i.A. brauchbare Lösung. Um dieses Verfahren allerdings sinnvoll einzusetzen, muss beim "rausnehmen und andere wieder reinpacken" ein Bookkeeping implementiert werden, um z.B. "1,2,3-raus 2,3,1 rein" zu verhindern, oder bisherige schlechtere Lösungen nochmals zu probieren.

[TheAn00bis]

Ein ganzes Buch als PDF zum Problem: http://www.or.deis.unibo.it/knapsack.html(Gefunden in der Wikpedia.)
Wollte ich dir nicht vorenthalten.

[semo]

ich würde auch sagen: backtracking, damit alle Möglichkeiten durchlaufen,
und dann wenn alle Möglichkeiten gefunden, den Wert mit dem nahesten Wert als Ergebnis liefern.

[alzaimar]

Ja, das ist die einzig beweisbare Möglichkeit für NP-komplette Probleme.

In der Praxis hat sich jedoch gezeigt, das es reicht, eine "hinreichend optimale" Lösung zu finden. Wenn ich sowieso drei (statt 5) LKW benötige (hinreichend optimal), dann ist es mir doch egal, wenn ob der eine LKW zu 55 oder 60% gefüllt ist.

Diese suboptimalen Algorithmen (auch zum 'Traveling Salesman') sind die Interessanten!

[rayman]

In der Wikipedia steht auch dieser Link:
http://www-i1.informatik.rwth-aachen...mus/algo15.php

Den Algorhitmus da find ich ziemlich gelungen. Basiert darauf, dass man die Gegenstände nacheinander reintut und jeweils beurteilt, ob die so entstandenen Teil-Menge(Beladungsmöglichkeit) im weiteren Verlauf überhautp eine Chance hat, optimal zu sein oder nicht.
Gucks dir mal an.

[buff222]

Nach einigen Schwierigkeiten und durchzechten Nächten habe ich das Programm jetzt fertig...
Ich möchte mich bei euch für eure Hilfe bedanken.
Ich habe einfach die 5 wertvollsten, also die kleinsten Quotienten aus Gewicht und Wert raussortierne lassen, die dann mitgenommen werden ...
Somit hab ich das problem mit dem maximal Gewicht rausgelassen... :-D
Meinem Lehrer reichts und damit is gut :wink:
Ich wusste nicht wie ich das hinkriege, vll. könnt ihr mir da ja noch helfen...

Hier mein kleines Progrämmchen...

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;                // Gegenstände mit Zufallswerten erzeugen
    Button2: TButton;                // Ergebnis bestimmen
    Button3: TButton;                // Programm beenden
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Ergebnis: array [1..5] of Integer;             // Speichert die Nummer der 5 wertvollsten
                                                    // Gegenstände vom Index 1 = wertvollster
                                                    // bis Index 5 = 5. wertvollster Gegenstand
  Ergebniswerte: array [1..5] of Real;          // Speichert die 5 niedrigsten Quotienten
                                                      // vom Index 1 = wertvollster bis Index
                                                      // 5 = 5. wertvollster Gegenstand
  Gewicht: array [1..10] of Integer;             // Das Gewicht der Gegenstände 1-10
  Quotient: array [1..10] of Real;             // Der Quotient (von Gewicht durch Wert) der
                                                  // Gegenstände 1-10
  Wert: array [1..10] of Integer;             // Der Wert der Gegenstände 1-10
  Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject);
var i: Integer;                   // i ist Schleifen-Hilfsvariable
begin
  Randomize;                   // Zufallszahlengenerator starten
  Memo1.Lines.Clear;                // Text aus Memo1 komplett löschen
  for i := 1 to 10 do                // den 10 Gegenständen Zufallswerte geben
    begin
    Gewicht[i] := Random(15)+1;             // damit Gewicht zwischen 1 und 15 liegt
    Wert[i] := Random(15)+1;             // damit Wert zwischen 1 und 15 liegt
    end;
  Memo1.Lines.Add('Die 10 Gegenstände haben folgende Eigenschaften:');
  Memo1.Lines.Add('');
  for i := 1 to 10 do
    Memo1.Lines.Add('Gegenstand '+IntToStr(i)+':    Gewicht: '
      +IntToStr(Gewicht[i])+'    Wert: '+IntToStr(Wert[i]));
end;

procedure TForm1.Button2Click(Sender: TObject);
var i, j: Integer;                   // i und j sind Schleifen-Hilfsvariablen
begin
  for i := 1 to 10 do // für die Gegenstände 1-10
    begin
    Quotient[i] := Gewicht[i]/Wert[i];          // ermittelt den Quotienten
    Memo1.Lines[1+i] := Memo1.Lines[1+i]+'    Quotient: '
      +FloatToStrF(Quotient[i], ffFixed, 10, 2);       // Real-Zahl wird auf 2 Stellen
                                                             // gerundet mit Genauigkeit 10
    end;
  for i := 1 to 5 do                // Bestimmung der 5 wertvollsten Gegenstände
    begin
    Ergebnis[i] := 1;                // gehe davon aus, dass direkt der 1. Gegenstand 
                                        // der Wertvollste ist
    Ergebniswerte[i] := Quotient[1];          // speichere den Quotienten des
                                                    // wertvollsten Gegenstandes
    for j := 2 to 10 do                // überprüfe die anderen 9 Gegenstände, ob sie 
                                          // nicht wertvoller sind
      if Ergebniswerte[i]>Quotient[j] then          // falls der aktuelle Gegenstand doch
                                                       // wertvoller ist, dann ...
        begin
        Ergebnis[i] := j;                // ... speichere den aktuellen Gegenstand und
        Ergebniswerte[i] := Quotient[j];          // speichere den aktuellen Quotienten
        end;
                // Jetzt wurden alle 10 Gegenstände überprüft. Der Wertvollste unter ihnen
                // wurde gefunden. Damit er nicht als nächst wertvoller Gegenstand
               // identifiziert wird ...
    Quotient[Ergebnis[i]] := 16;    // ... setze seinen Quotienten, der nun nicht
                                       // mehr gebraucht wird - da er bereits in die
                                       // "Top5-Liste" aufgenommen wurde - auf "16".
                                       // Somit ist er außerhalb der Skala 1-15 und
                                       // wird bei weiteren Schleifendurchläufen nicht
                                       // mehr als wertvoll eingestuft.
                // Durchlaufe die Schleife erneut, bis alle 5 wertvollsten Gegenstände
                // gefunden sind
    end;
  Memo1.Lines.Add('');
  Memo1.Lines.Add('');
  Memo1.Lines.Add('Die 5 wertvollsten Gegenstände lauten:');
  Memo1.Lines.Add('');
  for i := 1 to 5 do
    Memo1.Lines.Add(IntToStr(i)+': Gegenstand '+IntToStr(Ergebnis[i])+
      ' mit Quotient '+FloatToStrF(Ergebniswerte[i], ffFixed, 10, 2)); // Real-
      // Zahl wird auf 2 Stellen gerundet mit Genauigkeit 10
end;

procedure TForm1.Button3Click(Sender: TObject);
begin
  Close;
end;

end.

Vorschläge zur verbesserung des Programms nehm ich gerne an :)

ansonsten :thumb:

MfG buff222

[edit=sakura] [delphi]-Tags Mfg, sakura[/edit]