DTDOI - Đổi tiền

Tác giả: ladpro98

Ngôn ngữ: Pascal

program dtdoi;
uses    math;
const   maxn=111;
        maxV=10000;
        oo=1234567890;
        fi='';
var     a:array[1..maxn] of longint;
        f:array[0..maxn,0..maxV] of longint;
        n,s,maxA,res:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,s);
        for i:=1 to n do
        begin
                read(inp,a[i]);
                maxA:=max(maxA,a[i]);
        end;
        close(inp);
end;

procedure process;
var     i,j,t:longint;
begin
        //greedy
        if s>maxV then
        begin
                t:=(s-maxV) div maxA;
                s:=s-maxA*(t+1);
                res:=t+1;
        end;
        //dp
        f[0,0]:=0;
        for j:=1 to s do
        f[0,j]:=oo;
        for i:=1 to n do
        for j:=1 to s do
        begin
                f[i,j]:=f[i-1,j];
                if j>=a[i] then
                f[i,j]:=min(f[i,j],f[i,j-a[i]]+1);
        end;

end;

begin
        input;
        process;
        write(res+f[n,s]);
end.

Download