Задание 6: Выбор оптимального варианта

Типичная формулировка звучит так: дана таблица с объектами (людьми, экскурсиями, билетами, товарами), у каждого объекта есть один или несколько признаков (языки, достопримечательности, аттракционы) и числовая характеристика (стоимость, время). Нужно собрать набор объектов так, чтобы:

• вместе они покрывали определённый набор признаков (например, все четыре языка, все четыре аттракциона, не менее трёх достопримечательностей);
• суммарная числовая характеристика (стоимость, время) не превышала заданный лимит.

…

• Определение: комбинация — это набор из нескольких объектов (переводчиков, билетов, экскурсий), выбранных из таблицы.
• Суммарная стоимость набора из объектов со стоимостями $a_1, a_2, \dots, a_k$ считается по формуле: $$S = a_1 + a_2 + \dots + a_k$$
• Суммарное время набора считается аналогично: $$T = t_1 + t_2 + \dots + t_k$$
• Условие "объекты вместе покрывают набор признаков" означает, что объединение множеств признаков каждого объекта должно содержать все требуемые признаки. Если признаки объекта $i$ образуют множество $P_i$, а требуемый набор признаков — множество $Q$, условие записывается так: $$Q \subseteq P_1 \cup P_2 \cup \dots \cup P_k$$
• В задаче может требоваться не полное покрытие, а частичное — например, "не менее трёх из четырёх признаков", тогда достаточно, чтобы объединение содержало хотя бы 3 элемента из $Q$.
• Ограничение по бюджету или времени — это неравенство вида $S \le S_{max}$ или $T \le T_{max}$, где $S_{max}$, $T_{max}$ — заданные в условии числа.
• Важно: задача просит найти хотя бы один подходящий набор, а не все возможные и не единственно верный (кроме случаев, когда явно сказано "единственный набор").
• Один объект в таблице может содержать сразу несколько признаков (например, билет открывает доступ сразу к двум аттракционам) — это ключевая особенность, которая позволяет сократить число объектов в наборе и уложиться в бюджет.

1. Внимательно прочитайте условие: выпишите, какие признаки (языки, аттракционы, достопримечательности) должны быть охвачены набором, и какое ограничение (бюджет, время) задано.
2. Изучите таблицу: для каждого объекта отметьте, какие признаки он закрывает, и его числовую характеристику (стоимость или время).
3. Найдите объекты с наибольшим числом нужных признаков — они самые "выгодные" кандидаты для основы набора.
4. Составьте предварительный набор из одного-двух таких объектов и проверьте, какие признаки ещё не покрыты.
5. Подберите дополнительные объекты для покрытия оставшихся признаков, стараясь минимизировать добавляемую стоимость/время.
6. Просуммируйте стоимость (или время) собранного набора и сравните с лимитом из условия.
7. Если лимит превышен — замените один из объектов на более дешёвую альтернативу или попробуйте другую комбинацию с шага 3. …