Задача 23.  Путешественник из Москвы хочет посетить четыре города Золотого кольца России: Владимир, Ярославль, Суздаль и Ростов. Турагентство предлагает маршруты с посещением некоторых городов Золотого кольца. Сведения о стоимости билетов и маршрутах представлены в таблице.

Номер маршрута Посещаемые города Стоимость (руб)
1 Суздаль, Ярославль, Владимир 3900
2 Ростов, Владимир 2400
3 Ярославль, Владимир 2100
4 Суздаль 1650
5 Ростов, Суздаль 2700
6 Ярославль, Ростов 2350

Какие маршруты должен выбрать путешественник, чтобы побывать во всех четырех городах и затратить менее 5000 рублей?

В ответе укажите какой-нибудь один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.

Ответ

ОТВЕТ:  35.

Решение

Мы не можем выбрать три маршрута, потому что их минимальная стоимость будет \(2100 + 1650 + 2350 = 6100\), это больше 5000 рублей. Значит нужно покрыть все города Золотого кольца двумя маршрутами. Маршрут 1 выбрать нельзя, потому что на четвертый город денег не хватит. Также нельзя выбрать маршрут 4, потому что оставшихся денег не хватит ещё на три города. Таким образом остались маршруты 2, 3, 5 и 6. Можно взять маршруты 3 и 5, что дает возможность посетить все четыре города, затратив \(2100 + 2700 = 4800\) рублей.

Ответ:  35.