Rucksackproblem, Bitte um Hilfe

[Susan1990]

Hallo Leute.
Ich habe ein großes Problem und benötige dringend Hilfe:
Und zwar soll ich das Rucksackproblem programmieren. Also das mit der Profildichte lässt sich ja relativ einfach lösen. Aber ist das dann wirklich die optimale Lösung, den Rucksack zu packen?
Ein weiteres Problem ist, dass ich das rekursiv lösen muss. Weiß zwar was das bedeutet, aber nicht wie ich das in Delphi umsetzen kann.
Bin leider noch eine blutige Anfängerin in Delphi.
Kann mir jemand helfen?

lg Susan

[STS301]

wie willst du packen, aufs Bild klicken und dann zum Rucksack ziehen oder per Button?

[Susan1990]

Also das mit dem aufs Bild klicken wäre optimal, habe aber keine Ahnung wie ich das programmiertechnisch umsetzen muss. Aber mit Buttons ist ich denke mal auch OK.

[quendolineDD]

Das wäre dann "Drag and Drop". Dazu müsste hier im Forum schon eine Menge stehen. Vielleicht findest du sogar noch ein Programierbeispiel mit Quelltext zum anschauen und begreifen ;)

Aber mal zur Problemstellung: Was meinst du mit dem "Rucksackproblem"? Bzw. was ist dabei die Aufgabenstellung?

[Susan1990]

Es geht einfach darum, wie man einen Rucksack ideal packen muss, um dabei den meisten "Profit" oder Nutzen zu haben.
Hier ist das gut erklärt:
http://www-i1.informatik.rwth-aachen...mus/algo15.php

Bloß wie funktioniert das dann rekursiv???

[Susan1990]

Gibt es hier niemanden mehr, der mir helfen könnte?

Die Susan.

[BenjaminH]

Pushen ist erst nach 24h erlaubt :roll:
Wenn du in der Wikipedia nach deinem Problem gesucht hättest, hättest du dort den Link zu einem Algorithmus gefunden, der dir das löst. Auch bei Google bekommst du ganz schnell Lösungen.

[Susan1990]

Das bei Wikipedia habe ich schon gefunden, nur leider hilf mir das bezüglich der Rekursion nicht weiter...
Was haltet ihr eigentlich davon, solch eine Aufgabe in Info zu bekommen? Ich finde diese Aufgabe viel, viel zu schwer für Anfänger.

[grenzgaenger]

was für 'ne schule machst denn, dass du solche aufgaben bekommst?

ein blick hierdrauf, sollte helfen. <HTH>

.pas rucksackproblem

[blawen]

Zitat:

Zitat von Susan1990

Das bei Wikipedia habe ich schon gefunden, nur leider hilf mir das bezüglich der Rekursion nicht weiter...
Was haltet ihr eigentlich davon, solch eine Aufgabe in Info zu bekommen? Ich finde diese Aufgabe viel, viel zu schwer für Anfänger.

Zeig doch mal wie weit Du gekommen bist, dann kann/wird Dir ev. sogar irgendwer weiterhelfen (können)

[Susan1990]

Zitat:

Zitat von grenzgaenger

was für 'ne schule machst denn, dass du solche aufgaben bekommst?

ein blick hierdrauf, sollte helfen. <HTH>

.pas rucksackproblem

Danke für den Link.
Ich gehe 11. Klasse Gymnasium und habe dort ganz normal Informatik Grundkurs. Nur leider ist unser Lehrer nicht so toll... Der lässt überhaupt nicht mit sich reden und gibt uns meiner Meinung nach viel zu schwere Aufgaben, die er nichtmal selbst lösen könnte...

Die Lösung bei deinem Link ist doch aber nicht rekursiv gelöst oder? Habe echt keinen Plan wie man das rekursiv löst.

Susan

[grenzgaenger]

doch, die lösung ist rekursiv.

Delphi-Quellcode:

  PROCEDURE try (stufe: Integer; vektor: vektortyp);
  VAR wahl,gewicht,wert: Integer;

   :
   :
   :
  BEGIN  { T }
    FOR wahl:=auswahlanfang TO auswahlende DO
    BEGIN
      vektor[0]:=stufe;     { Stelligkeit setzen }
      vektor[stufe]:=wahl;  { Auswahl Objekt i treffen }
      vektor_bewerten;
      IF vollstaendig
        THEN BEGIN IF neues_optimum THEN  loesung_speichern   END
        ELSE BEGIN IF lebend        THEN  try(stufe+1,vektor) END //hier wird die routine selbst aufgerufen
    END
  END;

BEGIN
  :
  :
  try(1,vektor);     { rekursive Lösungssuche }

das heisst nichts anderes, als dass sich die routine selbst aufruft. hier noch ein Link

PS: möcht zwar nix sagen, aber didaktisch ist diese aufgabe verfehlt.

[Susan1990]

Hmmmm... Habe irgendwie noch Probleme den Quelltext zu verstehen.
Wie ist denn zum Bsp. der Vektor zu verstehen und das letzte Begin { Überschrift und kurze Hinweise }... Was macht denn das Program dort?

Trotzdem muss ich euch und das Forum ersteinmal sehr, sehr loben. Das ich so schnell Antworten bekomme, hätte ich nicht gedacht.

Susan

[grenzgaenger]

schon hier mal die SuFu getestet?

rucksackproblem oder rucksackproblem