MODULE ranac;
FROM InOut IMPORT WriteString, WriteCard, WriteLn, ReadString;
FROM FIO IMPORT File, Open, RdInt, Close, Exists;
FROM Str IMPORT Length;

CONST
  MaxPredmeta=20;
  MaxKapacitet=100;
TYPE
  niz=ARRAY [0..MaxPredmeta] OF CARDINAL;
  matrica=ARRAY[0..MaxPredmeta],[0..MaxKapacitet] OF CARDINAL;
  String = ARRAY [1..80] OF CHAR;
VAR
  fn : String;
  Kapacitet,BrPredmeta,UkTezina,UkVrednost: CARDINAL;
  vrednosti,tezine,redosled: niz;
  ok: BOOLEAN;

PROCEDURE ruksak( vrednosti,tezine: niz;
                  BrPredmeta,kapacitet: CARDINAL;
                  VAR redosled: niz;
                  VAR UkTezina,UkVrednost: CARDINAL;
                  VAR ok: BOOLEAN );

VAR
   i,j,pom: CARDINAL;
   tabela: matrica;
BEGIN

    IF(0<kapacitet)&(kapacitet<=MaxKapacitet)&(0<BrPredmeta)&(BrPredmeta<=MaxPredmeta)THEN
		i:=1;
		WHILE(tezine[i]>0)&(0<vrednosti[i]) & (i<BrPredmeta) DO
			INC(i);
		END;
		ok := (tezine[i]>0)&(vrednosti[i]>0);
	 ELSE
		ok := FALSE;
    END;

    IF ok THEN
                FOR j:= 0 TO kapacitet DO
			tabela[0,j] := 0;
		END;
		FOR i := 0 TO BrPredmeta DO
			tabela[i,0] := 0;
		END;
		FOR i := 1 TO BrPredmeta DO
			FOR j := 1 TO kapacitet DO
				tabela[i,j] := tabela[i-1,j];
				IF j >= tezine[i] THEN
					pom := tabela[i-1,j-tezine[i]] + vrednosti[i];
					IF pom > tabela[i,j] THEN
						tabela[i,j] := pom;
					END;
				END;
			END;
		END;

     	        UkTezina := 0;
		i := BrPredmeta;
		j := kapacitet;
		WHILE i > 0 DO
			IF tabela[i,j] # tabela[i-1,j] THEN
				redosled[i] := 1;
				UkTezina := UkTezina + tezine[i];
				j := j-tezine[i];
			ELSE
				redosled[i] := 0;
			END;
			DEC(i);
		END;
		UkVrednost := tabela[BrPredmeta, kapacitet];
    END;
END ruksak;

PROCEDURE ucitaj(fn:String; VAR granica, objekata: CARDINAL;
	VAR vrednosti, tezine : niz):BOOLEAN;
VAR
	F: File;
	brojac:CARDINAL;
BEGIN
  IF Exists(fn) THEN
		F:=Open(fn);
		granica:=RdInt(F);
		objekata:=RdInt(F);
		FOR brojac:=1 TO objekata DO
				vrednosti[brojac]:=RdInt(F);
				tezine[brojac]:=RdInt(F);
		END;
		Close(F);
		RETURN TRUE;
  ELSE
		RETURN FALSE;
  END;
END ucitaj;

PROCEDURE IspisiRedosled(red:niz;BrPredmeta:INTEGER);
VAR
  brojac: INTEGER;
BEGIN
	  WriteString("Redni brojevi: ");WriteLn;
	  FOR brojac:=1 TO BrPredmeta DO
		IF red[brojac]=1 THEN
		  WriteCard(brojac,2);
		  WriteLn;
		END;
	  END;
END IspisiRedosled;

BEGIN
  WriteString("unesite ime fajla:");
  WriteLn;
  ReadString(fn);

  IF Length(fn) = 0 THEN
	fn := "r1.txt";
  END;
  IF ucitaj(fn,Kapacitet,BrPredmeta,vrednosti,tezine) THEN
		  UkTezina:=0;
		  UkVrednost:=0;
		  ruksak(vrednosti,tezine,BrPredmeta,Kapacitet,redosled,UkTezina,UkVrednost,ok);
		  IF ok THEN
		  	  IspisiRedosled(redosled,BrPredmeta);
			  WriteLn;
			  WriteString("Ukupna vrednost je: ");
			  WriteCard(UkVrednost,4);
			  WriteLn;
			  WriteString("Ukupna zauzece kapaciteta je ");
			  WriteCard(UkTezina,4);
			  WriteLn;
		  ELSE
			  WriteString("greska u podacima");
			  WriteLn;
		  END;
  ELSE
   		WriteString("Neuspesno ucitavanje iz fajla");
   		WriteLn;
  END;
END ranac.