MODULE FullRanac;
FROM InOut IMPORT WriteString, ReadString, WriteLn, WriteInt;
FROM FIO IMPORT File, Open, Close, Exists, RdInt;

CONST
  MaxKapacitet = 100;
  MaxPredmeta = 20;

TYPE
  niz = ARRAY [0..MaxPredmeta] OF INTEGER;
  matrica = ARRAY [0..MaxPredmeta],[0..MaxKapacitet] OF INTEGER;
  String = ARRAY [1..100] OF CHAR;

VAR
  tezina, vrednost, izabrani:niz;
  kapacitet, brojpredmeta, ukupnavrednost, ukupnatezina: INTEGER;
  ok:BOOLEAN;

PROCEDURE Ucitaj(VAR vrednost, tezina: niz; VAR kapacitet, brojpredmeta: INTEGER; VAR ok: BOOLEAN);
VAR
  ime: String;
  i: INTEGER;
  f: File;
BEGIN
  ok:=FALSE;
  WriteString('Unesite ime fajla: ');
  WriteLn;
  ReadString(ime);
  IF Exists(ime) THEN
    ok:= TRUE;
    f:= Open(ime);
    kapacitet:= RdInt(f);
    IF (kapacitet <= 0) OR (kapacitet > MaxKapacitet) THEN
      ok:=FALSE;
    END;
    brojpredmeta:= RdInt(f);
    IF (brojpredmeta <= 0) OR (brojpredmeta > MaxPredmeta) THEN
      ok:=FALSE;
    END;
    FOR i:=1 TO brojpredmeta DO
      vrednost[i]:= RdInt(f);
      tezina[i]:= RdInt(f);
      IF (vrednost[i] <= 0) OR (tezina[i] <=0) THEN
        ok:=FALSE;
      END;
    END;
    Close(f);
  END;
END Ucitaj;

PROCEDURE Stampaj(brojpredmeta, ukupnavrednost, ukupnatezina:INTEGER; izabrani:niz);
VAR
  i:INTEGER;
BEGIN
  WriteString("Ukupna vrednost je: ");
  WriteInt(ukupnavrednost,0);
  WriteLn;
  WriteString("Ukupna tezina je: ");
  WriteInt(ukupnatezina,0);
  WriteLn;
  WriteString("Redni brojevi izabranih predmeta su: ");
  FOR i:=1 TO brojpredmeta DO
    IF izabrani[i] = 1 THEN
      WriteInt(i,0);
      WriteLn;
    END;
  END;
END Stampaj;

PROCEDURE Ranac(vrednost,tezina: niz; kapacitet, brojpredmeta: INTEGER;
                VAR izabrani: niz; VAR ukupnatezina, ukupnavrednost: INTEGER);
VAR
  i, j, pom: INTEGER;
  op:matrica;
BEGIN
  FOR j:=0 TO kapacitet DO
    op[0,j]:= 0;
  END;
  FOR i:=0 TO brojpredmeta DO
    op[i,0]:= 0;
  END;
  FOR i:=1 TO brojpredmeta DO
    FOR j:=1 TO kapacitet DO
      op[i,j]:= op[i-1,j];
      IF j >= tezina[i] THEN
        pom:= op[i-1,j-tezina[i]] + vrednost[i];
    IF pom > op[i,j] THEN
      op[i,j]:= pom;
    END;
      END;
    END;
  END;
  ukupnatezina:= 0;
  i:= brojpredmeta;
  j:= kapacitet;
  WHILE i>0 DO
    IF op[i,j] # op[i-1,j] THEN
      izabrani[i]:= 1;
      ukupnatezina:= ukupnatezina + tezina[i];
      j:= j - tezina[i];
    ELSE
      izabrani[i]:= 0;
    END;
    DEC(i);
  END;
  ukupnavrednost:= op[brojpredmeta, kapacitet];
END Ranac;


BEGIN

  Ucitaj(vrednost, tezina, kapacitet, brojpredmeta, ok);
  IF ok THEN
    Ranac(vrednost, tezina, kapacitet, brojpredmeta, izabrani, ukupnatezina, ukupnavrednost);
    Stampaj(brojpredmeta, ukupnavrednost, ukupnatezina, izabrani);
  END;

END FullRanac.