Задача №07825

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

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

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

Обозначим музеи: Эрмитаж (Э), Русский музей (Р), Петропавловская крепость (П), Исаакиевский собор (И).

Список маршрутов и их стоимость:
1. И — 300 руб.
2. П, И — 1,550 руб.
3. Э, Р — 1,400 руб.
4. П, Р — 1,500 руб.
5. Э — 300 руб.
6. Р — 400 руб.

Требуется выбрать набор маршрутов, чтобы покрыть все четыре музея $\{\text{Э; Р; П; И}\}$ с минимальной общей стоимостью.

Сравним стоимость отдельных маршрутов и комбинаций:

1. Для посещения Эрмитажа и Русского музея можно выбрать маршрут 3 за 1,400 руб. или комбинацию маршрутов 5 и 6 за $300+400=700$ руб. Очевидно, что выгоднее брать 5 и 6 по отдельности.

2. Для посещения Петропавловской крепости и Исаакиевского собора можно выбрать маршрут 2 за 1,550 руб. или комбинацию из маршрута 1 (Исаакиевский собор) и маршрута, содержащего П.

Рассмотрим возможные наборы для полного покрытия:

• Набор маршрутов 1, 4 и 5:
  Покрывают И (1), П и Р (4), Э (5). Все музеи включены.

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

• Набор маршрутов 2, 5 и 6:
  Покрывают П и И (2), Э (5), Р (6). Все музеи включены.

$$1550+300+400=2250\text{ руб.}$$

• Набор маршрутов 2 и 3:
  Покрывают П и И (2), Э и Р (3). Все музеи включены.

$$1550+1400=2950\text{ руб.}$$

Сравнивая полученные результаты, видим, что наименьшая сумма составляет 2,100 руб., что достигается при выборе маршрутов 1, 4 и 5.

Ответ: 145