Пишу скриптик, который выдаст мне победную стратегию для игры Dota Underlords.
Правила игры:
В игре 72 героя. У каждого героя есть 2 или больше альянсов. Альянсы активируются, когда на столе от одного до трёх героев с одним и тем же альянсом. На стол выставляется до 10 героев, герои не дублируются.
Пример:
Для простоты набираем 3 героев из возможных 4 и все альянсы требуют 2 героев:
Суккуб (маги, нечисть)
Фея (маги, насекомые)
Скелет (воины, нечисть)
Мечник (воины, человек)
Здесь лучшим набором из 3 героев будут Суккуб, Скелет и Мечник, потому что они дадут 3 альянса — маги, нечисть, воины.
Так вот, возвращаясь к задаче. Я хочу найти такие наборы из 10 героев, в которых количество альянсов будет максимальным.
Это не значит, что такая комбинация героев самая сильная, но мне интересно посмотреть на такие комбинации и дальше их проанализировать самостоятельно.
Я попробовал решить задачу в лоб, составить все возможные наборы из 10 героев и посчитать по ним альянсы. Проблема в том, что при таком подходе очень много вычислений. Пользуясь комбинаторикой получаем, что надо проверить 72! / (62! * 10!) = 536211932256 наборов. Написал сначала на js, потом на python используя multiprocessing, слишком много времени на оптимизацию тратить не стал, но последняя версия программы должна по расчетам занять где-то 10 часов на макбуке. Можно пробовать улучшить код, но…
…кажется, эта задача решается математически с помощью линейного программирования (linear programming). Так ли это? Можете помочь приложить этот метод на мою задачу?