Выбор площадок: условие и решение
Все площадки, величины и баллы вымышлены. Это самостоятельная задача, не действующий тест компании.
Полное условие: выбрать четыре площадки
Команда планирует один учебный цикл измерений и должна выбрать ровно четыре из девяти площадок. У каждой заданы тип, полная стоимость посещения, нагрузка на комплект оборудования и ценность данных. Все величины условные; баллы — критерий только этой задачи.
Типы: R — городской, S — пригородный, T — удалённый. В выбранном наборе должен присутствовать хотя бы один объект каждого типа. Нельзя выбрать одну площадку дважды.
| Площадка | Тип | Стоимость | Нагрузка | Баллы |
|---|
| A | R | 5 | 3 | 12 |
| B | S | 4 | 2 | 10 |
| C | T | 6 | 4 | 15 |
| D | R | 3 | 2 | 7 |
| E | S | 5 | 3 | 13 |
| F | T | 4 | 3 | 9 |
| G | T | 3 | 2 | 11 |
| H | R | 7 | 4 | 18 |
| I | S | 2 | 1 | 4 |
Суммарная стоимость не больше 18, нагрузка не больше 10. Равенство допускается. Посещение G требует включить B: там находится точка настройки оборудования. C и F нельзя включать вместе, потому что для них в условии требуются несовместимые комплекты.
Стоимость уже включает все затраты посещения; нагрузка складывается. Дополнительных расходов на сочетания, порядка посещения, расстояний и времени в пути нет. Поэтому задача выбирает набор, а не кратчайший маршрут. Увеличивать бюджет, арендовать второй комплект или отменять обязательный тип нельзя.
Цель — получить наибольшую сумму баллов среди допустимых наборов. Дополнительного правила выбора между равными максимумами нет. Если оптимальных наборов несколько, нужно перечислить их и не объявлять один единственно верным.
Сдать нужно выбранный набор, проверку каждого ограничения, доказательство сравнения с альтернативами и ответ при уменьшении допустимой нагрузки до девяти.
Сначала выполнимость, затем ценность
Быстро выбрать четыре самых высоких балла недостаточно. H, C, E, A дают 58, но стоят 23 и требуют нагрузку 14. Большая сумма не компенсирует два нарушения.
Есть и менее очевидные ошибки. Набор A, D, E, G укладывается в стоимость 16 и нагрузку 10, содержит все типы и даёт 43 балла. Но G требует B, которого нет. Набор A, B, C, F содержит обязательные типы, однако одновременно включает несовместимые C и F; кроме того, его нагрузка 12 превышает десять, а стоимость 19 — бюджет 18.
Первая допустимая комбинация тоже не обязательно лучшая. B, D, F, I стоит 13, требует нагрузку 8 и даёт 30. Она удовлетворяет правилам, но это лишь нижняя граница уже найденного результата. Освободившиеся деньги не являются сами по себе целью.
Удобный порядок проверки: число площадок → все три типа → зависимость G от B → несовместимость C/F → стоимость → нагрузка → сумма баллов. Последний показатель сравнивай только для прошедших наборов. Так причина отказа не теряется за привлекательной оценкой.
Полное решение и равные максимумы
Число всех наборов по четыре из девяти — 126. В этой задаче можно перебрать каждый без эвристики. После всех ограничений остаются 23 допустимых набора; максимальная сумма — 46 баллов. Её дают два варианта.
A, B, E, G: стоимость 5 + 4 + 5 + 3 = 17; нагрузка 3 + 2 + 3 + 2 = 10; баллы 12 + 10 + 13 + 11 = 46. R представлен A, S — B и E, T — G. Зависимость G выполнена через B. Несовместимой пары нет.
B, D, G, H: стоимость 4 + 3 + 3 + 7 = 17; нагрузка 2 + 2 + 2 + 4 = 10; баллы 10 + 7 + 11 + 18 = 46. R представлен D и H, S — B, T — G. B присутствует, C и F отсутствуют.
И стоимость, и нагрузка этих двух наборов совпадают. Выбрать первый по алфавиту можно как способ упорядочить вывод программы, но не как деловое преимущество: такого критерия в условии нет. Полный ответ сохраняет оба.
В списке допустимых планов приведены все 23 варианта с суммами. Это позволяет проверить не только найденные максимумы, но и утверждение «лучше нет». Переборщик работает на Python 3.9 без сторонних библиотек и выводит результаты из исходного JSON.
Доказательство полноты не сводится к слову «перебор». Если порядок не важен, число сочетаний равно 9 × 8 × 7 × 6 / (4 × 3 × 2 × 1) = 126. В генераторе каждый набор берётся один раз, проверяется по всем правилам, а максимум ищется среди прошедших. Для независимой сверки можно вместо сочетаний рассмотреть все 512 подмножеств девяти объектов и оставить только содержащие четыре. Если оба способа дают один список допустимых наборов и одинаковые максимумы, это дополнительно защищает от ошибки обхода. Всё равно сравни сами девять строк с условием: два способа могут одинаково правильно обработать неверно переписанную цифру.
Пример законченного ответа:
При исходной нагрузке десять найдено два равных лучших набора: A–B–E–G и B–D–G–H. Каждый стоит 17, использует всю допустимую нагрузку и даёт 46. Оба содержат три типа и выполняют зависимость G от B. Перебраны все 126 сочетаний, допустимы 23; ни одно не даёт больше 46. Для единственного выбора требуется дополнительный критерий, которого пока нет.
Новая вводная: комплект выдерживает девять
Оба прежних максимума требуют нагрузку 10 и становятся недопустимыми. Недостаточно зачеркнуть одну единицу в итоговой строке: нужно заново выбрать ровно четыре площадки и пересчитать остальные правила.
При нагрузке не больше девяти остаются 11 допустимых наборов. Максимум — 43 балла, и он единственный: B, G, H, I.
Проверка: стоимость 4 + 3 + 7 + 2 = 16; нагрузка 2 + 2 + 4 + 1 = 9; баллы 10 + 11 + 18 + 4 = 43. H даёт тип R, B и I — S, G — T. Зависимость G выполнена, несовместимой пары нет.
Ответ на изменение:
Отзываю прежние два варианта: они не проходят новую нагрузку. При девяти выбираю B–G–H–I: стоимость 16, нагрузка 9, баллы 43. Проверка всех сочетаний оставляет 11 допустимых наборов, среди них это единственный максимум. Уменьшение результата с 46 до 43 связано с новым ограничением, а не с ошибкой первоначального расчёта.
Здесь видно качество пересмотра: правило изменилось явно, прежний результат сохранён как версия, новый вывод доказан по тем же данным. Не нужно защищать старый набор после изменения условия.