DTDOI - Đổi tiền
Tác giả: ll931110
Ngôn ngữ: C++
#include <iostream>
#define MAXN 101
#define MAXV 10000
#define MAXK 1000000000
using namespace std;
int F[MAXV],a[MAXN],n,s;
int main()
{
int i,j,k,max,res;
//freopen("dtdoi.inp","r",stdin);
//freopen("dtdoi.out","w",stdout);
scanf("%d%d", &n, &s);
max = 0;
for (i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (max < a[i] && a[i] <= s) max = a[i];
}
for (i = 0; i < MAXV; i++) F[i] = MAXK;
F[0] = 0;
for (i = 1; i < MAXV; i++)
for (j = 1; j <= n; j++)
if (i >= a[j])
if (F[i] > F[i - a[j]] + 1) F[i] = F[i - a[j]] + 1;
if (s >= MAXV)
{
k = ((s - MAXV) / max) + 1;
s -= k * max;
}
else k = 0;
res = MAXK;
do
{
if (res > k + F[s]) res = k + F[s];
k++;
s -= max;
}
while (s >= 0);
printf("%d", res);
}