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

Решение:

Туристу нужно посетить 4 музея: Эрмитаж (Э), Русский музей (РМ), Петропавловскую крепость (ПК), Исаакиевский собор (ИС).

Рассмотрим предложенные маршруты и их состав:

• Маршрут 1: Эрмитаж (Э). Стоимость: 300 руб.
• Маршрут 2: Эрмитаж (Э), Русский музей (РМ). Стоимость: 1450 руб.
• Маршрут 3: Исаакиевский собор (ИС). Стоимость: 350 руб.
• Маршрут 4: Петропавловская крепость (ПК), Исаакиевский собор (ИС). Стоимость: 1300 руб.
• Маршрут 5: Русский музей (РМ). Стоимость: 350 руб.
• Маршрут 6: Петропавловская крепость (ПК), Русский музей (РМ). Стоимость: 1600 руб.

Нам нужно посетить все 4 музея, а именно: Э, РМ, ПК, ИС. Проверим, какие комбинации маршрутов позволяют это сделать с наименьшей суммой.

Вариант 1:

• Маршрут 2 (Э, РМ) + Маршрут 4 (ПК, ИС) = 1450 + 1300 = 2750 руб.

Вариант 2:

• Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС) = 300 + 350 + 350 + 1300 = 2300 руб. (Здесь ПК и ИС посещаются дважды, что нерационально).

Вариант 3:

• Маршрут 2 (Э, РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС) = 1450 + 350 + 1300 = 3100 руб. (Здесь ИС посещается дважды).

Вариант 4:

• Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 6 (ПК, РМ) = 300 + 350 + 350 + 1600 = 2600 руб. (Здесь РМ посещается дважды).

Вариант 5:

• Маршрут 1 (Э) + Маршрут 2 (Э, РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС) - не подходит, так как музеи повторяются.

Вариант 6:

• Попробуем комбинировать отдельные посещения и маршруты:
• Маршрут 2 (Э, РМ) = 1450 руб.
• Маршрут 4 (ПК, ИС) = 1300 руб.
• Итого: 1450 + 1300 = 2750 руб.
• Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС). Это посещение одного музея дважды.

Рассмотрим наилучшие варианты для покрытия всех 4 музеев:

• Эрмитаж (Э), Русский музей (РМ), Петропавловская крепость (ПК), Исаакиевский собор (ИС).
• Маршрут 2 (Э, РМ) + Маршрут 4 (ПК, ИС) = 1450 + 1300 = 2750 руб. (Все 4 музея посещены, без повторов).
• Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС). Здесь ИС повторяется.
• Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 6 (ПК, РМ). Здесь РМ повторяется.
• Маршрут 1 (Э) + Маршрут 2 (Э, РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС). Здесь Э и ИС повторяются.

Проанализируем комбинации, которые охватывают все 4 музея с минимальной стоимостью:

• Маршрут 2 (Э, РМ) + Маршрут 4 (ПК, ИС) = 1450 + 1300 = 2750.
• Маршрут 2 (Э, РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС) - Повтор ИС.
• Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС) - Повтор ИС.
• Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 6 (ПК, РМ) - Повтор РМ.
• Если мы берем все отдельные музеи: Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС). Оставшаяся ПК. Для ПК есть Маршрут 6 (ПК, РМ) и Маршрут 4 (ПК, ИС).
• 1 + 5 + 3 + 6: 300 + 350 + 350 + 1600 = 2600. (РМ повтор).
• 1 + 5 + 3 + 4: 300 + 350 + 350 + 1300 = 2300. (ИС повтор).

Посмотрим на комбинацию, где мы берем самые выгодные отдельные музеи и дополняем их:

• Эрмитаж: 300 (Маршрут 1)
• Русский музей: 350 (Маршрут 5)
• Исаакиевский собор: 350 (Маршрут 3)
• Петропавловская крепость: нам нужна отдельно.

Маршрут 4 (ПК, ИС) = 1300. В нем есть ИС. Если взять Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 4 (ПК, ИС), то это 300 + 350 + 1300 = 2000. Но ПК не посещен.

Проверим еще раз:

• Маршрут 2 (Э, РМ) = 1450
• Маршрут 3 (ИС) = 350
• Маршрут 4 (ПК, ИС) - Повтор ИС.

Нужно охватить все 4 объекта: Э, РМ, ПК, ИС.

Рассмотрим наборы, которые включают все 4 объекта:

• Маршрут 2 (Э, РМ) + Маршрут 4 (ПК, ИС) = 1450 + 1300 = 2750.
• Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС) - Повтор ИС.
• Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 6 (ПК, РМ) - Повтор РМ.

Попробуем скомбинировать наименьшие стоимости для отдельных музеев и маршрутов:

• Маршрут 1 (Э) = 300
• Маршрут 5 (РМ) = 350
• Маршрут 3 (ИС) = 350
• Маршрут 4 (ПК, ИС) = 1300 (содержит ПК и ИС)
• Маршрут 6 (ПК, РМ) = 1600 (содержит ПК и РМ)

Если взять: Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 4 (ПК, ИС) = 300 + 350 + 1300 = 2000. В этом случае мы посетим Э, РМ, ПК, ИС. Стоимость 2000 руб. Этот вариант посещает все 4 музея.

Если взять: Маршрут 1 (Э) + Маршрут 3 (ИС) + Маршрут 6 (ПК, РМ) = 300 + 350 + 1600 = 2250. В этом случае мы посетим Э, ИС, ПК, РМ. Стоимость 2250 руб.

Сравнивая 2000 и 2250, минимальная стоимость 2000 руб.

Набор маршрутов: 1, 5, 4.

Проверим, можно ли сделать еще дешевле:

• Маршрут 2 (Э, РМ) = 1450
• Маршрут 3 (ИС) = 350
• Маршрут 4 (ПК, ИС) = 1300
• Маршрут 6 (ПК, РМ) = 1600

Вариант: Маршрут 2 (Э, РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС) = 1450 + 350 + 1300 = 3100 (ИС повтор).

Вариант: Маршрут 2 (Э, РМ) + Маршрут 3 (ИС) + Маршрут 6 (ПК, РМ) = 1450 + 350 + 1600 = 3400 (РМ повтор).

Вариант: Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС) = 300 + 350 + 350 + 1300 = 2300 (ИС повтор).

Вариант: Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 6 (ПК, РМ) = 300 + 350 + 350 + 1600 = 2600 (РМ повтор).

Вариант: Маршрут 1 (Э) + Маршрут 2 (Э, РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС) - Повторы Э и ИС.

Вариант: Маршрут 1 (Э) + Маршрут 2 (Э, РМ) + Маршрут 3 (ИС) + Маршрут 6 (ПК, РМ) - Повтор РМ.

Наименьшая стоимость достигается при выборе маршрутов, которые охватывают все 4 музея без повторов или с наименьшим количеством повторов:

1. Маршрут 2 (Э, РМ) + Маршрут 4 (ПК, ИС) = 1450 + 1300 = 2750.
2. Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 4 (ПК, ИС) - сумма 2300, но ИС повторяется.
3. Маршрут 1 (Э) + Маршрут 5 (РМ) + Маршрут 3 (ИС) + Маршрут 6 (ПК, РМ) - сумма 2600, но РМ повторяется.

Рассмотрим вариант 1 + 5 + 3. Это посещение трех музеев: Э, РМ, ИС. Стоимость 300 + 350 + 350 = 1000 руб.

Нам нужно добавить ПК. Для этого есть Маршрут 4 (ПК, ИС) за 1300 руб. или Маршрут 6 (ПК, РМ) за 1600 руб.

• Если взять Маршрут 4: 1 + 5 + 3 + 4 = 300 + 350 + 350 + 1300 = 2300 руб. (ИС повторяется).
• Если взять Маршрут 6: 1 + 5 + 3 + 6 = 300 + 350 + 350 + 1600 = 2600 руб. (РМ повторяется).

Рассмотрим комбинацию маршрутов 1, 5, 4:

• Маршрут 1 (Э) = 300
• Маршрут 5 (РМ) = 350
• Маршрут 4 (ПК, ИС) = 1300
• Итого: 300 + 350 + 1300 = 2000 руб.
• Этот набор посещает: Эрмитаж, Русский музей, Петропавловскую крепость, Исаакиевский собор. Все 4 музея посещены.

Рассмотрим комбинацию маршрутов 1, 3, 6:

• Маршрут 1 (Э) = 300
• Маршрут 3 (ИС) = 350
• Маршрут 6 (ПК, РМ) = 1600
• Итого: 300 + 350 + 1600 = 2250 руб.
• Этот набор посещает: Эрмитаж, Исаакиевский собор, Петропавловскую крепость, Русский музей. Все 4 музея посещены.

Сравнивая 2000 и 2250, минимальная стоимость – 2000 руб.

Набор маршрутов: 1, 5, 4.

Ответ: 154