Rucksackproblem

[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 von Luckie:

Zitat von buff222:

Ich hätte gern einen ganzen Quellcode , 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...
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.

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...
Meinem Lehrer reichts und damit is gut
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

MfG buff222

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