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

Beispielprogramm 1.1:   5coins



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

Teilmengenproblem: Gegeben sind N Münzen mit den Münzwerten
p1 , p2 , .. , pN  und ein Betrag B. Gesucht ist eine Möglichkeit,
den Betrag B mit möglichst wenig Münzen auszuzahlen. Bei dieser
Übungsaufgabe sind bestimmte Daten als Konstanten vorgegeben. }

CONST  N             =  5;    { Gegeben sind 5 Münzen }
       B             =  130;  { Zielbetrag }
       auswahlanfang =  0;    { Objekt nicht gewählt }
       auswahlende   =  1;    { Objekt gewählt }
TYPE   vektortyp     =  ARRAY [0..N] OF Integer;
CONST  pvektor       :  ARRAY [1..N] OF Integer = (100,70,60,40,30); { Werte }
VAR    vektor        :  vektortyp;
       i             :  Integer;
       akt_optimum   :  Integer;
       loesung       :  vektortyp;

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

    { T.1 }
    PROCEDURE vektor_bewerten;
    VAR j: Integer;
    BEGIN
      anzahl:=0; wert:=0;
      FOR j:=1 TO vektor[0]
      DO BEGIN
           anzahl:=anzahl+vektor[j];        { Anzahl der Münzen berechnen }
           wert:=wert+vektor[j]*pvektor[j]  { Münzwerte aufsummieren }
         END
    END;

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

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

    { T.4 }
    FUNCTION lebend: Boolean;
    BEGIN  lebend := (anzahl<akt_optimum) AND (wert<=B)  END;

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

  BEGIN  { T }
    FOR wahl:=auswahlanfang TO auswahlende DO
    BEGIN
      vektor[0]:=stufe;     { Stelligkeit setzen }
      vektor[stufe]:=wahl;  { Auswahl wahl für Objekt stufe 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 :  Teilmengenproblem');
           Writeln('---------------------------------');
  Writeln('Gegeben sind N=',N,' Münzen mit den Werten: ');
  FOR i:=1 TO n-1 DO Write(pvektor[i],', ');
  Writeln(pvektor[i],'  und ein');
  Writeln('Betrag B=',B,'. Gesucht ist eine Möglichkeit den Betrag B mit');
  Writeln('möglichst wenig Münzen auszuzahlen.'); Writeln;
  { Initialisierung, Lösungssuche }
  vektor[0]:=0;      { Start mit 0-stelligem Vektor }
  akt_optimum:=N+1;  { Ergebnis N+1 1 Münzen bedeutet keine Lösung }
  try(1,vektor);     { rekursive Lösungssuche }
  { Ausgabe der Lösung }
  IF akt_optimum>N
    THEN writeln('keine Lösung !')
    ELSE BEGIN
      FOR i:=1 TO N DO
        IF loesung[i]=0 THEN Write('-':6)
                        ELSE Write(pvektor[i]:6);
        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