Шешімі: Выбор маршрутов по стоимости
Путешественник из Москвы хочет посетить 4 города Золотого кольца России: Владимир, Ярославль, Суздаль и Ростов Великий. Турагентство предлагает маршруты с посещением некоторых городов Золотого кольца. Сведения о стоимости билетов и маршрутах представлены в таблице. Какие маршруты должен выбрать путешественник, чтобы побывать во всех четырёх городах и затратить менее 6000 рублей?
| Номер маршрута | Посещаемые города | Стоимость (руб.) |
|---|---|---|
| 1 | Ярославль, Владимир | 2100 |
| 2 | Суздаль, Ярославль, Владимир | 3650 |
| 3 | Ростов, Суздаль | 2800 |
| 4 | Ростов, Владимир | 2350 |
| 5 | Ярославль, Ростов | 2350 |
| 6 | Суздаль | 1550 |
Шешім по шагам
3 қадамМаршрут 1 включает Ярославль и Владимир, а маршрут 3 — Ростов и Суздаль. Таким образом, вместе эти маршруты охватывают все четыре города.
Складываем стоимость выбранных маршрутов:
$$2100 + 2800 = 4900$$Полученная сумма меньше 6000 рублей, поэтому подходит набор маршрутов 1 и 3.
$$4900 < 6000$$Где здесь ошибаются
Выбрать маршруты 2 и 5: они охватывают все города, но стоят ровно 6000 рублей, а требуется менее 6000.
Не проверить, что выбранные маршруты вместе посещают все төрт города.