Решение: Оптимальный выбор маршрутов
Турист, прибывший в Санкт-Петербург, хочет посетить 4 музея: Эрмитаж, Русский музей, Петропавловскую крепость и Исаакиевский собор. Экскурсионные кассы предлагают маршруты с посещением одного или нескольких объектов. Какие маршруты должен выбрать путешественник, чтобы посетить все четыре музея и затратить на все билеты наименьшую сумму?
| Номер маршрута | Посещаемые объекты | Стоимость (руб.) |
|---|---|---|
| 1 | Эрмитаж | 250 |
| 2 | Эрмитаж, Исаакиевский собор | 1300 |
| 3 | Петропавловская крепость, Русский музей | 1500 |
| 4 | Петропавловская крепость, Исаакиевский собор | 1500 |
| 5 | Русский музей | 350 |
| 6 | Исаакиевский собор | 600 |
В ответе укажите ровно один набор номеров маршрутов без пробелов, запятых и других дополнительных символов.
Решение по шагам
3 шагаМаршрут 3 позволяет посетить Петропавловскую крепость и Русский музей. Для посещения Эрмитажа и Исаакиевского собора можно выбрать маршруты 1 и 6.
$$250 + 1500 + 600 = 2350$$Другой очевидный набор — маршруты 2 и 3: он покрывает все четыре музея, но стоит дороже.
$$1300 + 1500 = 2800$$Следовательно, наименьшая стоимость достигается при выборе маршрутов 1, 3 и 6.
$$2350 < 2800$$Где здесь ошибаются
Выбрать маршруты 2 и 3, не сравнив их стоимость с набором 1, 3 и 6.
Записать номера маршрутов с пробелами или запятыми.