147. Доллары
Валюта Новой Зеландии
состоит из купюр 100$, 50$, 20$, 10$, 5$ и монет 2$, 1$, 50c, 20c, 10c, 5c.
Необходимо определить количество способов, которыми можно составить заданную
сумму. Например, 20 центов можно представить четырьмя способами: 20, 10 + 10,
10 + 5 + 5, 5 + 5 + 5 + 5.
Вход. Состоит из нескольких действительных чисел,
представляющих собой денежную сумму в долларах. Каждая входная сумма не более
300.00$ и кратна 5 центам. Последний тест содержит сумму 0.00 и не
обрабатывается.
Выход. Для
каждого теста вывести денежную сумму, выровненную справа в поле длины 6, и
число способов ее представления, выровненную справа в поле длины 17.
Пример входа
0.20
2.00
0.00
Пример выхода
0.20 4
2.00 293
РЕШЕНИЕ
динамическое программирование
Анализ алгоритма
Обозначим через f(k, n) количество
способов составить сумму n из первых k номиналов монет. Оно равно
количеству способов составить сумму n первыми (k – 1) номиналами
плюс количество способов составить сумму (n – ak) k
номиналами. Имеем соотношение:
f(k, n) = f(k – 1, n) + f(k,
n – ak)
|
k \ n |
|
|
|
|
|
|
|
|
|
|
f[k
- 1, n] |
|
|
|
f[k,
n – ak] |
|
|
f[k,
n] |
|
|
|
|
|
|
|
|
Изначально положим f(0, 0)
= 1, f(n, 0) = 0, n > 0.
Пример
Сумму s = 20 можно выдать 4 способами:
1) 20
2) 10 + 10
3) 10 + 5 + 5
4) 5 + 5 + 5 +5
|
|
k \ n |
0 |
5 |
10 |
15 |
20 |
|
начало |
0 |
1 |
0 |
0 |
0 |
0 |
|
c = 5 |
1 |
1 |
1 |
1 |
1 |
1 |
|
c = 10 |
2 |
1 |
1 |
2 |
2 |
3 |
|
c = 20 |
3 |
1 |
1 |
2 |
2 |
4 |
Остальные номиналы не
повлияют на результат для суммы в 20 центов.
Реализация алгоритма
Ячейка mas[i] будет содержать количество способов,
которыми можно выдать сумму i. Размер массива установим MAX = 30001.
Номиналы монет (в центах) занесем в массив coins.
const int MAX = 30001;
long long mas[MAX];
int coins[11]
= {5,10,20,50,100,200,500,1000,2000,5000,10000};
Динамически пересчитываем массив mas для каждого
номинала (всего 11 номиналов) согласно соотношению, приведенному в анализе
алгоритма.
memset(mas,0,sizeof(mas));
mas[0] = 1;
for(i = 0; i < 11; i++)
{
for(j = coins[i]; j < MAX; j++)
mas[j] += mas[j -
coins[i]];
}
Читаем входные суммы v, преобразовываем их в
целое число центов n и печатаем результат mas[n] в соответствии с
требуемым форматом.
while(scanf("%lf",&v),
v > 0)
{
n = (int)(v * 100 + 0.1);
printf("%6.2lf%17lld\n",v,mas[n]);
}