Турист, прибывший в Санкт-Петербург, хочет посетить 4 музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и составе маршрутов представлены в таблице. | Номер маршрута | Посещаемые объекты | Стоимость (руб.) | | :--- | :--- | :--- | | 1 | Петропавловская крепость, Исаакиевский собор | 1350 | | 2 | Эрмитаж, Русский музей | 1600 | | 3 | Русский музей | 300 | | 4 | Эрмитаж, Исаакиевский собор | 1650 | | 5 | Петропавловская крепость | 250 | | 6 | Исаакиевский собор | 650 | Какие маршруты должен выбрать путешественник, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму? В ответе укажите ровно один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.
Для решения задачи необходимо найти такую комбинацию маршрутов, которая включает все четыре объекта (Эрмитаж, Русский музей, Петропавловская крепость, Исаакиевский собор) с минимальной суммарной стоимостью. 1. Составим список объектов: Эрмитаж (Э), Русский музей (Р), Петропавловская крепость (П), Исаакиевский собор (И). 2. Проанализируем маршруты, содержащие Эрмитаж, так как это обязательный объект, а он представлен только в двух вариантах: — маршрут 2 (Э, Р): стоимость 1600 руб. ; — маршрут 4 (Э, И): стоимость 1650 руб. . 3. Рассмотрим варианты набора всех музеев, начиная с маршрута 2 (Э, Р). Для завершения набора нужно посетить П и И: — можно взять маршрут 1 (П, И) за 1350 руб. . Итого: 1600 + 1350 = 2950 руб. ; — можно взять маршрут 5 (П) за 250 руб. и маршрут 6 (И) за 650 руб. . Итого: 1600 + 250 + 650 = 2500 руб. . 4. Рассмотрим варианты набора всех музеев, начиная с маршрута 4 (Э, И). Для завершения набора нужно посетить Р и П: — маршрут 3 (Р) стоит 300 руб. , а маршрут 5 (П) стоит 250 руб. . Итого: 1650 + 300 + 250 = 2200 руб. ; — других комбинаций для Р и П, не включающих уже имеющиеся объекты, нет (маршрут 2 содержит Р, но он дороже и дублирует Э). 5. Сравним полученные стоимости: 2950 , 2500 и 2200 руб. . Наименьшая сумма составляет 2200 руб. . Она соответствует набору маршрутов 3, 4 и 5. Ответ: 345
345
Турист, прибывший в Санкт-Петербург, хочет посетить 4 музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Сведения о стоимости билетов и составе маршрутов представлены в таблице.
| Номер маршрута | Посещаемые объекты | Стоимость (руб.) |
|---|
| 1 | Петропавловская крепость, Исаакиевский собор | 1350 |
| 2 | Эрмитаж, Русский музей | 1600 |
| 3 | Русский музей | 300 |
| 4 | Эрмитаж, Исаакиевский собор | 1650 |
| 5 | Петропавловская крепость | 250 |
| 6 | Исаакиевский собор | 650 |
Какие маршруты должен выбрать путешественник, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму? В ответе укажите ровно один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.