Skip to main content

Теория: Выбор оптимального варианта, поиск подходящего набора

Задание

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

Номер маршрутаПосещаемые объектыСтоимость
(тг.)
\(\displaystyle 1\)Петропавловская крепость\(\displaystyle 150\)
\(\displaystyle 2\)Исаакиевский собор, Петропавловская крепость\(\displaystyle 1450\)
\(\displaystyle 3\)Исаакиевский собор, Русский музей\(\displaystyle 1400\)
\(\displaystyle 4\)Русский музей\(\displaystyle 550\)
\(\displaystyle 5\)Эрмитаж\(\displaystyle 500\)
\(\displaystyle 6\)Эрмитаж, Русский музей\(\displaystyle 1400\)

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

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

Решение

Требуется подобрать набор маршрутов так, чтобы путешественник 

  • посетил \(\displaystyle 4\) музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор;
  • потратил на билеты наименьшую сумму. 

Начнём подбор набора с одного из объектов. Например, Петропавловской крепости.

Номер маршрутаПосещаемые объектыСтоимость
(тг.)
\(\displaystyle 1\)Петропавловская крепость\(\displaystyle 150\)
\(\displaystyle 2\)Исаакиевский собор, Петропавловская крепость\(\displaystyle 1450\)
\(\displaystyle 3\)Исаакиевский собор, Русский музей\(\displaystyle 1400\)
\(\displaystyle 4\)Русский музей\(\displaystyle 550\)
\(\displaystyle 5\)Эрмитаж\(\displaystyle 500\)
\(\displaystyle 6\)Эрмитаж, Русский музей\(\displaystyle 1400\)

Посетить Петропавловскую крепость можно на двух маршрутах – номер \(\displaystyle 1\) и \(\displaystyle 2{\small . }\)

Рассмотрим оба варианта, следя за итоговой стоимостью наборов.

При покупке маршрута \(\displaystyle 1\) придётся докупить маршруты \(\displaystyle 3\) и \(\displaystyle 5\)

При покупке маршрута \(\displaystyle 2\) придётся докупить маршруты \(\displaystyle 4 {\small,} \, 5\) или маршрут \(\displaystyle 6\)

Самая низкая общая стоимость составила \(\displaystyle 2050\) тенге.

Значит, дешевле посещение всех четырёх музеев обойдется при покупке маршрутов \(\displaystyle 1 {\small,} \, 3\) и \(\displaystyle 5{\small.}\) 

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

Ответ: \(\displaystyle 135\)