B a c k t r a c k i n g

Beispielprogramm 3:   knapsac



PROGRAM      knapsac;    {            "nur eine Lösung"
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
HMO ludens, Warendorf, 27.6.1988, ein Beispiel für  BACKTRACKING.

Rucksackproblem: Gegeben sind N Objekte mit den Werten  p1 , .. , pN
und den Gewichten  w1, .. , wN  und ein Wert B für das maximale
Gewicht.  Gesucht ist eine Auswahl von Objekten, bei denen das Gewicht
B nicht überschritten wird und der Gesamtwert maximal ist.
Bei dieser Übungsaufgabe sind die Daten als Konstanten vorgegeben. }

CONST  N             =  10;     { Gegeben sind 5 Münzen }
       B             =  200;    { Zielbetrag }
       auswahlanfang =  0;      { Objekt nicht nehmen }
       auswahlende   =  1;      { Objekt nehmen }
TYPE   vektortyp     =  ARRAY [0..N] OF Integer;
CONST  pvektor       :  ARRAY [1..N] OF Integer =      { Werte }
                        (100, 70, 60, 40, 35, 30, 30, 25, 20, 5);
       wvektor       :  ARRAY [1..N] OF Integer =      { Gewichte }
                        (110, 95, 85, 80, 55, 50, 45, 35, 20, 10);
VAR    vektor        :  vektortyp;
       i             :  Integer;
       akt_optimum   :  Integer;
       loesung       :  vektortyp;

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

    { T.1 }
    PROCEDURE vektor_bewerten;
    VAR j: Integer;
    BEGIN
      wert:=0; gewicht:=0;
      FOR j:=1 TO vektor[0]
        DO BEGIN  gewicht:= gewicht+ vektor[j]*wvektor[j];
                  wert   := wert   + vektor[j]*pvektor[j]
           END
    END;

    { T.2 }
    FUNCTION vollstaendig: Boolean;
    BEGIN  vollstaendig := (vektor[0]=N)  END;

    { T.3 }
    FUNCTION neues_optimum: Boolean;
    BEGIN  neues_optimum := (gewicht<=B) AND (wert>akt_optimum)  END;

    { T.4 }
    FUNCTION lebend: BOOLEAN;
    BEGIN  lebend := (gewicht<=B)  END;

    { T.5 }
    PROCEDURE loesung_speichern;
    BEGIN  akt_optimum:=wert;  loesung:=vektor  END;

  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
    END
  END;

BEGIN
  { Überschrift und kurze Hinweise }
  Writeln; Writeln('BACKTRACKING :  knapsac');
           Writeln('-----------------------');
  Writeln('Gegeben sind N=',N,' Objekte mit den Werten:');
  FOR i:=1 TO n-1 DO Write(pvektor[i],', ');
  Writeln(pvektor[i]);
  Writeln('und den Gewichten:');
  FOR i:=1 TO n-1 DO Write(wvektor[i],', ');
  Writeln(wvektor[i]);
  Writeln('und ein Betrag B=',B,'. Gesucht ist eine Auswahl der Objekte,');
  Writeln('deren Gewicht B nicht überschreitet und deren Wert maximal ist.');
  Writeln;
  { Initialisierung, Lösungssuche }
  vektor[0]:=0;      { Start mit 0-stelligem Vektor }
  akt_optimum:=0;    { Ergebnis 0 bedeutet keine Lösung }
  try(1,vektor);     { rekursive Lösungssuche }
  { Ausgabe der Lösung }
  IF akt_optimum=0
    THEN writeln('keine Lösung !')
    ELSE BEGIN
      Write('Werte:    ');
      FOR i:=1 TO N DO
        IF loesung[i]=0 THEN Write('-':6)
                        ELSE Write(pvektor[i]:6);
      Writeln;
      Write('Gewichte: ');
      FOR i:=1 TO N DO
        IF loesung[i]=0 THEN Write('-':6)
                        ELSE Write(wvektor[i]:6);
      Writeln;
      Writeln('maximaler Wert: ',akt_optimum); Writeln
    END
END.



HTML-Texte: Münzen 1 Münzen 2 ADT Stack Escher knapsac bunte Reihe salesman HAUPTTEXT
Paket mit Pascal-Dateien laden: BackPac.Zip   (47 K)

zur Informatik-Leitseite


© HMO, Neubearbeitung Januar 1998