Динамическое Программирование Найти Все Возможные Комбинации Команд
Я пытался решить задачу, в которой мне нужно вычислить количество возможных командных образований для случайного вида спорта.
Входные данные примерно такие:
P → Number of Team Players
R → Roles
[Min, Max] → Role 0
[Min, Max] → Role 1
...
[Min, Max] → Role r-1
----------
Min= Minimum number of Players for the Role
Max= Maximum number of Players for the Role
Возьмем к примеру Спорт1. Допустим, Sport1 - это 3 типа ролей (A, B, C), теперь представим, что в каждой команде по 8 игроков.
8 → Number of Team Players
3 → Roles
[3 , 7] → Role A
[1 , 5] → Role B
[0 , 2] → Role C
Допустимых команд: [
3-5-0,3-4-1,3-3-2,4-4-0,4-3-1,4-2-2,5-3-0,5-2-1,5-1-2,6-2-0,6-1-1,7-1-0]Число действует группа формаций: 12
Я уже решил эту задачу, Перейдя на каждую возможную формацию, и если сумма игроков в каждой роли равна числу игроков команды, то добавьте один к конечному результату. В противном случае добавьте ноль a. k. a. сделайте то же самое для следующей комбинации, пока не будет достигнут конец.
3+5+0 = 8 → действительное формирование команды .
3+5+1 > 8 → недопустимое формирование команды
3+4+0 инвалидная команда формирование
Это все забавы и игры, пока количество игроков не достигнет примерно 40, а количество ролей - примерно 20, а Min = 0 и Max = 40 для каждой роли.
Пример:
40
20
[0; 40] → Role A
[0; 40] → Role B
...
[0; 40] → Role T
В этом случае мне нужно было бы проверить 40^20 возможных образований, для которых я уже сделал некоторые сокращения, сделав только для роли a 0, а затем умножить на 20, но все еще нужно проверить 40^19 различных комбинаций.
Эта проблема должна быть решена. использование динамического программирования. Я уже использовал DP для решения некоторых проблем(проблемы последовательности, максимальная прибыль клубничных ящиков), но, похоже, не могу найти способ решить эту проблему.
Может ли кто-нибудь пролить свет на то, как решить эту проблему и/или аналогичные проблемы, которые я мог бы найти в интернете или в книге, которая могла бы помочь мне найти решение DP для этого?
1 ответ:
Задачи динамического программирования обычно заканчиваются тем, что вы упорядочиваете части задачи в последовательности, так что вы можете работать с ними слева направо, выполняя достаточно работы на этапе n, чтобы вы могли ссылаться на нее для получения всей информации на этапе n+1.
Здесь вы можете думать о первых n ролях как о первых n этапах, поэтому первые n строк, таких как" [Min, Max] → Role 0 " в вашем примере. На этапе n я бы вычислил, для всех доступных игроков до максимума P, число различные формации вы можете составить, используя только первые n ролей и до этого количества игроков.
На этапе n+1, для каждого количества доступных игроков, я бы рассмотрел все законные числа игроков в роли n+1. Вычитая это из числа игроков, которых я в данный момент рассматривал, я получаю число игроков, оставшихся для первых n ролей, и я ищу ответ, хранящийся там, чтобы получить количество различных образований для первых n ролей. Суммируя эти возможности, я получаю количество образований, которые я могу составить для первых N + 1 ролей, используя это количество игроков в общей сложности. Ясно, что я повторяю это для всех чисел до P, чтобы получить ответы, которые мне нужно сохранить для этапа n+1-если только это не финальный этап, в котором нужен только ответ для игроков P.
Если решения, которые вы принимаете, можно расположить слева направо по этапам, где ответ для каждого этапа не зависит от большого количества информации и может быть вычислен из ответа для предыдущих этапов, то динамический Программирование обычно является практическим способом решения проблемы. Вы можете превратить практически любую задачу в задачу динамического программирования, если вы готовы хранить и вычислять для очень большого числа возможностей на каждом этапе, но в конечном итоге это число становится настолько большим, что так называемое решение становится совершенно непрактичным.
В качестве примера, в задаче наверху второй этап-это следующая задача только с двумя ролями, A и B.
[3 , 7] → Роль A
[1 , 5] → Роль B
В исходной задаче вам нужно вычислить общее число различных командных образований, если P=8, то есть если у вас есть 8 игроков в команде. Задача второго этапа состоит в том, чтобы определить количество образований, если есть только две роли, но вам нужно определить количество образований для 0 игроков, для 1 игрока, для 2 игроков... до 8 игроков. Затем, когда вы приступите к разработке ответа для третьего этапа, вы можете сказать, например: "если я поставлю 3 игрока в роль C, у меня будет 5 игроки слева и две роли слева, и я могу посмотреть на ответ, который я уже рассчитал для двухролевой задачи с 5 игроками, чтобы увидеть, сколько образований есть с 3 игроками в роли С. "