Cái túi

Một vị tướng sái khi lập công được nhà vua ban 1 cái túi có thể tích V và cho phép chọn các vật quý trong số N đồ vật để bỏ vào túi. Mỗi đồ vật thứ i có giá trị (độ quý giá) và thể tích tương ứng là A[i], B[i]. Hãy giúp người tướng quân này chọn được các đồ vật sao cho thể tích của chúng không vượt quá V và có tổng giá trị là lớn nhất. Cho biết V, N là các số nguyên dương bé hơn 100 và A[i], B[i] là các số nguyên dương bé hơn 256.
Dữ liệu: Cho trong file CAITUI.INP gồm N+1 dòng
+ Dòng đầu tiên ghi 2 số N, V.
+ Trên N dòng tiếp theo mỗi dòng ghi 2 số A[i], B[i] (i=1,…N)
Kết qủa: Xuất ra màn hình dưới dạng sau:
+ Dòng đầu ghi dãy các số tương ứng với chỉ số các đồ vật được chọn.
+ Dòng thứ 2 ghi tổng giá trị của các đồ vật được chọn. Ví dụ
VD:
     CAITUI.INP
        5 100
        40 40
        70 30
        6  40
        48 23
        4  12
   Màn hình:
       Chọn các vật: 4 2 1
      Tổng trị giá: 158

                                                           Lời giải tham khảo

uses crt;
const
      fi='nhap.txt';
      fo='xuat.txt';
      max=100;
 var
    n,m,q,v,g,tv,tgt,maxgt,k: integer;
    a,b,x,t: array[0..max] of integer;
    c: array[1..max] of boolean;
    f: text;
 procedure Nhap;
          begin
               assign(f,fi);
               reset(f);
                        readln(f,n,v);
                        for g:=1 to n do readln(f,a[g],b[g]);
               close(f);
          end;
 procedure ss;
        begin
                if tv <=v then
                   if tgt>maxgt then
                        begin
                                maxgt:=tgt;
                                for g:=1 to n do t[g]:=x[g];
                        end

        end;
 procedure Try(i: integer);
        var j:integer;
        begin
                for j:=1 to n do
                        if c[j] then
                                begin
                                        if i=k then ss
                                        else
                                                begin
                                                        tgt:=tgt+a[j];
                                                        x[i]:=j;
                                                        tv:=tv+b[j];
                                                        c[j]:=false;
                                                        try(i+1);
                                                        c[j]:=true;
                                                        tgt:=tgt-a[j];
                                                        x[i]:=0;
                                                        tv:=tv-b[j];
                                                end;
                                end;
           end;
 begin
      clrscr;
      Nhap;
      for k:=1 to n do
        begin
                for g:=1 to n do
                        begin
                                x[g]:=0;
                                c[g]:=true;
                        end;
                tgt:=0;
                tv:=0;
                try(1);
        end;
      Write('Chon cac vat: ');
      For g:=1 to n do
        if t[g] <> 0 then write(t[g],'; ');
      writeln;
      write('Tong gia tri: ',maxgt);
      readln;
 end.