Подбор набора
В этих задачах из таблицы выбирают несколько строк: экскурсии, билеты, переводчиков, наборы инструментов. Набор должен покрыть все нужные объекты и уложиться в лимит денег или времени. Наборы перебирают по порядку, начиная с того объекта, который есть в меньшем числе строк.
Как подобрать набор
Покройте все объекты, потом проверьте сумму.
- Выпишите объекты, которые нужно покрыть: города, языки, аттракционы, инструменты.
- Найдите объект, который есть в меньшем числе строк. Каждый набор обязан содержать одну из этих строк.
- К каждой такой строке добавьте строки для оставшихся объектов и посчитайте сумму.
- Сравните сумму с лимитом. Если просят наименьшую сумму, сравните все полные наборы между собой.
- Номера строк пишут подряд в любом порядке: 236 и 362 — один и тот же набор.
Соберите набор
Каждый объект хотя бы в одной строке
Набор подходит, если каждый нужный объект есть хотя бы в одной выбранной строке и сумма не больше лимита. Начните с объекта, который встречается реже всех: тогда вариантов для перебора меньше.
Пример
Экскурсии: 1 — музей живописи и парк, 450 руб.; 2 — парк, 200 руб.; 3 — загородный дворец и музей живописи, 400 руб.; 4 — загородный дворец, 300 руб.; 5 — загородный дворец и крепость, 450 руб.; 6 — крепость, 200 руб. Подберите набор, чтобы посетить крепость, дворец, парк и музей живописи не дороже 850 рублей.
- 1.Крепость есть только в экскурсиях 5 и 6.
- 2.С экскурсией 5 (крепость и дворец) нужны ещё парк и музей: 1 даёт оба, но ; дают . Не подходит.
- 3.С экскурсией 6 (крепость) нужны дворец, парк и музей: дают . Подходит.
Ответ:
Набор с наименьшей суммой
Если лимита нет, а просят самый дешёвый полный набор, переберите все полные наборы и сравните суммы. Набор из двух предметов иногда дешевле, чем те же предметы по отдельности, а иногда дороже: это нужно посчитать.
Пример
Нужны лопата, тяпка, вилы и грабли. Наборы: 1 — грабли, 460 руб.; 2 — вилы и грабли, 880 руб.; 3 — лопата, 220 руб.; 4 — тяпка и грабли, 680 руб.; 5 — вилы и лопата, 740 руб.; 6 — тяпка, 340 руб. Соберите полный комплект с наименьшей суммой.
- 1.Вилы есть только в наборах 2 и 5.
- 2.С набором 5 нужны тяпка и грабли: (набор 4) или (наборы 6 и 1).
- 3.С набором 2 нужны лопата и тяпка: .
- 4.Наименьшая сумма : наборы 4 и 5.
Ответ:
Набор по времени: успеть за один день
Если лимит — время, сложите часы на выбранные экскурсии. Кроме суммы проверьте часы работы: каждую экскурсию нужно начать и закончить, пока объект открыт. Начинайте день с той экскурсии, которая раньше закрывается.
Пример
Экскурсия 1 — Эрмитаж, открыт 10:00–19:00, занимает 4 ч. Экскурсия 5 — Кунсткамера и Музей эмоций, открыты 9:00–17:30, занимает 6 ч. Можно ли за один день пройти обе экскурсии и посетить три достопримечательности?
- 1.Экскурсия 5 закрывается раньше: начинаем с неё в 9:00 и заканчиваем в 15:00, до 17:30.
- 2.Экскурсия 1: с 15:00 до 19:00, Эрмитаж открыт до 19:00.
- 3.Достопримечательностей три: Эрмитаж, Кунсткамера, Музей эмоций.
Ответ: да, набор
Проверьте себя
00