HỌC TIN CÙNG THỦ KHOA

Đề bài: Ở đất nước Omega người ta chỉ tiêu tiền xu. Có N loại tiền xu, loại thứ i có mệnh giá là ai đồng. Một người khách du lịch đến Omega du lịch với số tiền M đồng. Ông ta muốn đổi số tiền đó ra tiền xu Omega để tiện tiêu dùng. Ông ta cũng muốn số đồng tiền đổi được là ít nhất (cho túi tiền đỡ nặng khi đi đây đi đó). Bạn hãy giúp ông ta tìm cách đổi tiền.

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

const fi = 'DOITIEN.INP';
      fo = 'DOITIEN.OUT';
      MAXN = 10000;
      MAXW = 1000;
      oo = MAXINT div 2;
var f: text;
    n, m: integer;
    a: array[1..MAXN] of integer;
    L: array[0..MAXN, 0..MAXW] of integer;
    //L[i, j] la so dong tien khi doi

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

    function min(a, b: integer): integer;
    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:= 1 to m do L[0, j]:= +oo;
        // L[0, 0] = ?

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

    procedure TruyVet(i, j: integer);
    var t:integer;
    begin
        if i = 0 then exit;
        if j = 0 then exit;
        if j >= a[i] then
        begin
                if L[i, j] = 1 + L[i, j-a[i]] then // Chon loai tien thu i
                begin
                        TruyVet(i, j-a[i]);

                        writeln(f, 'chon loai tien ', i,
                                ' menh gia la ', a[i]);
                end
                        else TruyVet(i-1, j);
        end
                else // Khong chon loai tien thu i
                        TruyVet(i-1, j);
    end;

    procedure InKQ;
    var i, j:integer;
    begin
        assign(f, fo); rewrite(f);
        if L[n, m] = +oo then writeln(f, 'khong co cach doi')
        else
        begin
                writeln(f, L[n, m]);
                TruyVet(n, m);
        end;

        close(f);
    end;

BEGIN
        Nhap;
        QHD;
        InKQ;
END.