Задача №08144

Турист, прибывший в Санкт-Петербург, хочет посетить 4 музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и составе маршрутов представлены в таблице.

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

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

Турист должен посетить четыре объекта: Эрмитаж (Э), Русский музей (Р), Петропавловскую крепость (П), Исаакиевский собор (И). Маршруты и их стоимости:

1. Маршрут 1: Э — $250$ руб.
2. Маршрут 2: Э, И — $1300$ руб.
3. Маршрут 3: П, Р — $1500$ руб.
4. Маршрут 4: П, И — $1500$ руб.
5. Маршрут 5: Р — $350$ руб.
6. Маршрут 6: И — $600$ руб.

Нужно выбрать несколько маршрутов, чтобы в совокупности покрыть все четыре объекта и минимизировать общую стоимость.

1. Объекты Э и Р можно посетить отдельно по низкой цене: маршрут 1 (Э за $250$ руб.) и маршрут 5 (Р за $350$ руб.).

2. Для посещения П и И рассмотрим варианты:

• Маршрут 4 дает сразу П и И за $1500$ руб.
• Другие варианты: маршрут 3 (П и Р за $1500$ руб.) плюс маршрут 6 (И за $600$ руб.) = $2100$ руб., но при этом Р уже покрыт маршрутом 3, а маршрут 5 не нужен. Однако для Э потребуется маршрут 1, итого:

$$1500+600+250=2350\text{ руб.}$$

что дороже.

• Маршрут 2 (Э и И) невыгоден, так как стоимость $1300$ руб. больше, чем сумма отдельно за Э и И ($250+600=850$ руб.).

3. Самый дешевый способ получить П и И — маршрут 4 за $1500$ руб.

4. Тогда, добавляя маршруты 1 и 5 для Э и Р, получаем полный набор: маршруты 1, 4, 5. Сумма:

$$250+1500+350=2100\text{ руб.}$$

5. Проверим другие комбинации:

• Маршруты 1, 3, 6: $250+1500+600=2350$ руб. (дороже).
• Маршруты 2, 3: $1300+1500=2800$ руб. (дороже).
• Маршруты 1, 5, 6, 3: $250+350+600+1500=2700$ руб. (дороже).

6. Минимальная стоимость $2100$ руб. достигается при выборе маршрутов 1, 4, 5.

Ответ: 145