PROCEDURE  KNAPSAC(N,C,K : INTEGER; VAR S : CARGO ;
                    VAR SETT : MARK; VAR MAXSUM : INTEGER);
 CONST
   NN=100;
 TYPE
   CARGO=ARRAY[1..NN] OF INTEGER;
   MARK =ARRAY[1..NN] OF BOOLEAN;
 VAR
   I,J,M : INTEGER;
     SUM : INTEGER;
       T : MARK ;
  PROCEDURE  SORT;
   VAR
    U,V,W : INTEGER;
   BEGIN
    FOR V:=2  TO  N  DO
     FOR U:=N  DOWNTO  V  DO
      IF S[U]>S[U-1] THEN
       BEGIN
        W:=S[U];
        S[U]:=S[U-1];
        S[U-1]:=W
       END
   END;

  FUNCTION  BIN (DEC : INTEGER; VAR T : MARK) : INTEGER;
   VAR
    I,C : INTEGER;
   BEGIN
    FOR I:=1  TO  N  DO  T[I]:=FALSE;
    C:=0;
    I:=1;
    WHILE (DEC<>0) AND (I<=N) DO
     BEGIN
      IF DEC MOD 2 = 1  THEN
         BEGIN
          T[I]:=TRUE;
          C:=C+1
         END;
      DEC:=DEC DIV 2;
      I:=I+1
     END;
    BIN:=C
   END;

  FUNCTION  WA (T : MARK) : INTEGER;
   VAR
     SUM : INTEGER;
      K  : INTEGER;
   BEGIN
     SUM:=0;
     FOR K:=1  TO  N  DO
       IF  T[K]  THEN
         SUM:=SUM+S[K];
     WA:=SUM
   END;

 BEGIN
  SORT;
  MAXSUM:=0;
  M:=1;
  FOR I:=1  TO  N  DO  M:=M*2;
  FOR I:=0  TO M-1 DO
   IF (BIN(I,T)<=K) THEN
   IF (WA(T)<=C) THEN
     BEGIN
       SUM:=WA(T);
       FOR J:=1  TO  N  DO
        IF (NOT T[J]) AND (SUM+S[J]<=C) THEN
          BEGIN
            SUM:=SUM+S[J];
            T[J]:=TRUE
          END;
       IF MAXSUM<SUM THEN
         BEGIN
          MAXSUM:=SUM;
          FOR I:=1 TO N DO
              SETT[I]:=T[I]
         END
     END
  END;