Турист, прибывший в Санкт-Петербург, хочет посетить 4 музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и составе маршрутов представлены в таблице. | Номер маршрута | Посещаемые объекты | Стоимость (руб.) | | :--- | :--- | :--- | | 1 | Эрмитаж | 250 | | 2 | Эрмитаж, Исаакиевский собор | 1300 | | 3 | Петропавловская крепость, Русский музей | 1500 | | 4 | Петропавловская крепость, Исаакиевский собор | 1500 | | 5 | Русский музей | 350 | | 6 | Исаакиевский собор | 600 | Какие маршруты должен выбрать путешественник, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму? В ответе укажите ровно один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.
Турист должен посетить четыре объекта: Эрмитаж (Э), Русский музей (Р), Петропавловскую крепость (П), Исаакиевский собор (И). Маршруты и их стоимости: Маршрут 1: Э — 250 руб. Маршрут 2: Э, И — 1300 руб. Маршрут 3: П, Р — 1500 руб. Маршрут 4: П, И — 1500 руб. Маршрут 5: Р — 350 руб. Маршрут 6: И — 600 руб. Нужно выбрать несколько маршрутов, чтобы в совокупности покрыть все четыре объекта и минимизировать общую стоимость. Объекты Э и Р можно посетить отдельно по низкой цене: маршрут 1 (Э за 250 руб.) и маршрут 5 (Р за 350 руб.). Для посещения П и И рассмотрим варианты: Маршрут 4 дает сразу П и И за 1500 руб. Другие варианты: маршрут 3 (П и Р за 1500 руб.) плюс маршрут 6 (И за 600 руб.) = 2100 руб., но при этом Р уже покрыт маршрутом 3, а маршрут 5 не нужен. Однако для Э потребуется маршрут 1, итого: 1500 + 600 + 250 = 2350 руб. что дороже. Маршрут 2 (Э и И) невыгоден, так как стоимость 1300 руб. больше, чем сумма отдельно за Э и И ( 250 + 600 = 850 руб.). Самый дешевый способ получить П и И — маршрут 4 за 1500 руб. Тогда, добавляя маршруты 1 и 5 для Э и Р, получаем полный набор: маршруты 1, 4, 5. Сумма: 250 + 1500 + 350 = 2100 руб. Проверим другие комбинации: Маршруты 1, 3, 6: 250 + 1500 + 600 = 2350 руб. (дороже). Маршруты 2, 3: 1300 + 1500 = 2800 руб. (дороже). Маршруты 1, 5, 6, 3: 250 + 350 + 600 + 1500 = 2700 руб. (дороже). Минимальная стоимость 2100 руб. достигается при выборе маршрутов 1, 4, 5. Ответ: 145
145