Как найти максимум с заданными ограничениями в Python / Pandas

Question

Как найти «оптимальное» решение для данного набора игроков, позиций игроков, стоимости игрока, бюджета и набора ограничений?Например:

ID - Pos - cost - pts
1     1     13    10
2     1     5     13
3     2     10    15
4     2     10     8
5     3     12    12
6     3     7     14

и бюджет 30 (общая стоимость не может превышать 30), ограничение 1 игрок на позицию.

Реальная проблема, которую я пытаюсь решить:оценили очки на игрока в фэнтези-футболе.Теперь с учетом ограничений в фэнтези-футболе, то есть

1. бюджет 100
2. 1 вратарь
3. макс. 5 защитников, минимум 3 защитника
4. максимум 5 полузащитников, минимум 3 полузащитника
5. максимум 3 нападающих, минимум 1 нападающий

Учитывая эти ограничения, как мне найти максимальные очки?

Какие библиотеки и инструменты доступны для чего-то подобного?Я мог представить, что я делаю это в Excel Solver, но, учитывая мой набор данных с более чем 1000 игроков, это не сработает.

Я начал писать собственный код, но быстро понял, что для этого должны быть готовые решения.

Answer 1

Это в значительной степени проблема с рюкзаком (https://en.wikipedia.org/wiki/Knapsack_problem) с дополнительным ограничением, что одни и те же позиции не могут идти вместе, что обсуждалось здесь ранее:

Рюкзак с предметамирассмотреть ограничение

Как уже говорилось, проблема в NP-сложности.

Вы можете взглянуть на модуль itertools, чтобы уменьшить время выполнения ваших вычислений.

Answer 2

Scikit-optimize - хорошая отправная точка https://scikit -optimize.github.io /