HỌC TIN CÙNG THỦ KHOA

Đề bài: Cho n vật, vật i nặng ai và có giá trị bi. Hãy chọn ra một số vật để cho vào balô sao cho tổng khối lượng không vượt quá W và tổng giá trị là lớn nhất. Chú ý rằng mỗi vật có thể được chọn nhiều lần.

Mời các bạn download tại: Click here

const fi = 'VALI02.INP';
      fo = 'VALI02.OUT';
      MAXN = 10000;
      MAXW = 1000;
var f: text;
    n: integer;
    W: integer;
    a: array[1..MAXN] of integer; // Trong luong cac do vat
    b: array[1..MAXN] of real; // Gia tri cac do vat
    L: array[0..MAXN, 0..MAXW] of real;

    procedure Nhap;
    var i: integer;
    begin
        assign(f, fi); reset(f);
        readln(f, n, W);
        for i:= 1 to n do
                readln(f, a[i], b[i]);
        close(f);
    end;

    function max(a, b: real): real;
    begin
        if a > b then exit(a)
                else exit(b);
    end;


    procedure QHD;
    var i, j: integer;
    begin
        for i:= 0 to n do L[i, 0]:= 0;
        for j:= 0 to w do L[0, j]:= 0;

        for i:= 1 to n do
                for j:= 1 to W do
                begin
                        L[i, j]:= L[i-1, j];
                        if a[i] <= j then
                                L[i, j]:= max(b[i] + L[i, j-a[i]],
                                              L[i-1, j]);
                end;
    end;

    procedure TruyVet(i, j: integer);
    begin
        if i = 0 then exit;
        if j = 0 then exit;
        if L[i, j] = b[i] + L[i, j-a[i]] then // Chon do vat thu i
        begin
                TruyVet(i, j-a[i]);
                writeln(f, 'Chon do vat thu ', i, ' voi trong luong la ',
                           a[i], ' va gia tri la ', b[i]:0:2);
        end
                else // Khong chon do vat thu i
                        TruyVet(i-1, j);
    end;

    procedure InKQ;
    var i, j:integer;
    begin
        assign(f, fo); rewrite(f);
        writeln(f, L[n, W]:0:2);
        TruyVet(n, W);
        {for i:=1 to n do begin
            for j:=1 to w do write(f, L[i,j]:6:2);
            writeln(f);
        end;  }
        // Chon ra trong n do vat sao cho trong luong khong vuot qua W
        // va gia tri thu duoc la lon nhat
        close(f);
    end;

BEGIN
        Nhap;
        QHD;
        InKQ;
END.