Задача по теории алгоритмов: бананы для Марины
Марина купила тур в Банановую страну с 5 по 22 октября. Ввозить и вывозить бананы через границу запрещено. Банановый король в начале каждого месяца издаёт указ о ценах. Цена одного банана в местной валюте на нужные числа октября приведена в таблице:
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 8,1 8 7 8,1 9 8 8,1 7,2 7 8 9 8,1 9 8 9 8,2 7 7,1 Марина хочет ежедневно съедать по одному банану. Она любит только зелёные бананы, поэтому согласна съесть банан только в течение 4 дней после покупки. Например, банан, купленный 5 октября, Марина согласна съесть 5, 6, 7 или 8 октября. Марина может запасаться бананами, когда они подешевле.
В какие дни по сколько бананов надо покупать Марине, чтобы потратить как можно меньше денег?
Показать ответ
В дни с 5 по 22 октября нужно купить, соответственно, 1, 1, 4, 0, 0, 1, 0, 1, 4, 1, 0, 0, 0, 3, 0, 0, 2, 0 бананов.
Разобрать решение
Чтобы решить задачу, достаточно правильно на неё посмотреть. Вместо того, чтобы думать, сколько бананов покупать в каждый день, давайтедля каждого дня выберем, в какой из дней купить банан!
Для этого надо выбрать самую низкую цену из четырёх: текущего дня и трёх предыдущих (если предыдущих дней меньше трёх, то смотрим только на те, что есть).
Для каждого дня на диаграмме ниже стрелкой указана самая низкая цена из доступных. Соответственно, в каждый из дней следует купить столько бананов, сколько стрелок указывают на цену под этим днём.
Получаем ответ:
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| 1 | 1 | 4 | 0 | 0 | 1 | 0 | 1 | 4 | 1 | 0 | 0 | 0 | 3 | 0 | 0 | 2 | 0 |
Обсуждение
0Комментариев пока нет.