home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power-Programmierung
/
CD1.mdf
/
modula2
/
library
/
modula1
/
selectio.mod
< prev
next >
Wrap
Text File
|
1987-06-11
|
2KB
|
86 lines
(* Find an optimal selection of objects from a given set of n objects
under a given constraint. Each object is characterised by two
properties v (for value) and w (for weight). The optimal selection
is the one with the largest sum of values of its members. The
constraint is that the sum of their weights must not surpass
a given limit limv. The algorithm is called branch and bound. *)
MODULE selection;
FROM InOut IMPORT WriteString, WriteCard, ReadCard, WriteLn, Write;
CONST n = 10;
TYPE index = [1..n];
object = RECORD
v,w: CARDINAL
END;
soi = SET OF index;
VAR i: index;
a: ARRAY index OF object;
limw,totv,maxv,w1,w2,w3: CARDINAL;
s,opts: soi;
z: ARRAY [0..1] OF CHAR;
PROCEDURE try(i: index; tw,av: CARDINAL);
VAR av1: CARDINAL;
BEGIN
IF tw + a[i].w <= limw THEN
INCL(s,i);
IF i < n THEN
try(i+1,tw+a[i].w,av)
ELSE
IF av > maxv THEN
maxv := av;
opts := s
END;
EXCL(s,i)
END
END;
av1 := av - a[i].v;
IF av1 > maxv THEN
IF i < n THEN
try(i+1,tw,av1)
ELSE
maxv := av1;
opts := s
END
END
END try;
BEGIN
totv := 0;
FOR i := 1 TO n DO
WITH a[i] DO
WriteString(' Enter the value> '); ReadCard(v);
WriteString(' Enter the weight> '); ReadCard(w);
WriteLn;
totv := totv + v
END
END;
WriteString(' Enter weights 1, 2, 3 > ');
ReadCard(w1); ReadCard(w2); ReadCard(w3);
WriteLn;
z[0] := '*'; z[1] := ' ';
WriteLn; WriteString(' weight > ');
FOR i := 1 TO n DO WriteCard(a[i].w,4) END;
WriteLn; WriteString(' value> ');
FOR i := 1 TO n DO WriteCard(a[i].v,4) END;
WriteLn;
REPEAT
limw := w1;
maxv := 0;
s := soi{}; opts := soi{};
try(1,0,totv);
WriteCard(limw,6);
FOR i := 1 TO n DO
WriteString(' ');
IF i IN opts THEN Write(z[0]) ELSE Write(z[1]) END;
END;
WriteLn;
w1 := w1 + w2;
UNTIL w1 > w3
END selection.