прикладная задача
На прошлой неделе возвращались домой с Юрцом и начальником моим с работы. Юрцу нужно было снять денег с банкомата. Пока он деньги снимал, я задумался над такой вот задачкой:
Пусть банкомат выдает купюры номиналов n_1, ... n_k в неограниченном количестве. Пусть n_(l) кратен n_(l-1). Для любого 1 < l <= k. Какой стратегией нужно пользоваться, чтобы снять заданной количество каждой купюры за минимальное поличество шагов.
Решение
Для начала рассмотрим задачу, когда нам нужно снять только m купюр с номиналом n_l, 1<= lНапример, для номинала 10 рублей нам никак не снять больше, чем 4 купюры, т.к. дальше они стекуются в полтос :)
Таким образом мы снимем всю нашу сумму за m / (n_(l+1) / n_l - 1) округленное "наверх" шагов. Назовем это число Min_l.
Если l=k, то можно сразу снять столько купюр, сколько нужно, т.к. купюры старшего номинала не "стекуются". Min_l = 1.
Теперь расссмотрим общий случай, т.е. задачу из начала поста. Заметим, что номинилы не влияют друг на друга, т.е. мы все еще каждый шаг для любого номинала n_l , 1 <= l < k можем снять от 0 до n_(l+1) / n_l - 1 купюр. И для максимального номинала мы мыжем снять сколько угодно купюр. Получается, что наличие других купюр не уменьшает и не увеличивает Min_l. Предлагается жадная стратегия - снимать по максимуму каждой купюры за шаг. В таком случае, количество шагов у нас будет max_(1 <= l <= k) (Min_l). Стратегия является оптимальной, т.к. в противном случае существует l такое, что купюру с номиналом n_l можно снять за количество шагов меньшее Min_l, что невозможно.
Пример использования: банкомат выдает 5000, 1000, 500, 100, 50 рэ. Нужно снять 10 десяток, 6 соток, 20 пятитысячников(ого!).
1 шаг:
5000- 20
100 - 4
10 - 4
2 шаг:
100 - 2
10 - 4
3 шаг:
10 - 2
Задачка простенькая, но мне захотелось поделиться своими рассуждениями :D
Пусть банкомат выдает купюры номиналов n_1, ... n_k в неограниченном количестве. Пусть n_(l) кратен n_(l-1). Для любого 1 < l <= k. Какой стратегией нужно пользоваться, чтобы снять заданной количество каждой купюры за минимальное поличество шагов.
Решение
Для начала рассмотрим задачу, когда нам нужно снять только m купюр с номиналом n_l, 1<= lНапример, для номинала 10 рублей нам никак не снять больше, чем 4 купюры, т.к. дальше они стекуются в полтос :)
Таким образом мы снимем всю нашу сумму за m / (n_(l+1) / n_l - 1) округленное "наверх" шагов. Назовем это число Min_l.
Если l=k, то можно сразу снять столько купюр, сколько нужно, т.к. купюры старшего номинала не "стекуются". Min_l = 1.
Теперь расссмотрим общий случай, т.е. задачу из начала поста. Заметим, что номинилы не влияют друг на друга, т.е. мы все еще каждый шаг для любого номинала n_l , 1 <= l < k можем снять от 0 до n_(l+1) / n_l - 1 купюр. И для максимального номинала мы мыжем снять сколько угодно купюр. Получается, что наличие других купюр не уменьшает и не увеличивает Min_l. Предлагается жадная стратегия - снимать по максимуму каждой купюры за шаг. В таком случае, количество шагов у нас будет max_(1 <= l <= k) (Min_l). Стратегия является оптимальной, т.к. в противном случае существует l такое, что купюру с номиналом n_l можно снять за количество шагов меньшее Min_l, что невозможно.
Пример использования: банкомат выдает 5000, 1000, 500, 100, 50 рэ. Нужно снять 10 десяток, 6 соток, 20 пятитысячников(ого!).
1 шаг:
5000- 20
100 - 4
10 - 4
2 шаг:
100 - 2
10 - 4
3 шаг:
10 - 2
Задачка простенькая, но мне захотелось поделиться своими рассуждениями :D