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.