Динамическое программирование Найти все возможные комбинации команд

Question

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

вход что-то вроде этого:

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 

---

Возьмем, к примеру Sport1. Скажем, 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 +-> 8 → недействительной команда формирование

3 + 4 + 0 < 8 → недействительной команда формирование

---

Это все развлечения и игры, пока число игроков идет на что-то вроде 40 и число ролей примерно на 20, а Min = 0 и Max = 40 для каждой роли.

Пример:

40 
20 
[0; 40] → Role A 
[0; 40] → Role B 
... 
[0; 40] → Role T 

В этом случае я должен был бы проверить на 40^20 возможных образований для Wich я уже сделал некоторые сокращения, делая только для роли А0, а затем умножить на 20, но до сих пор необходимо проверить 40^19 различных комбинаций.

Эта проблема должна быть решена с использованием динамического программирования. Я уже использовал DP для решения некоторых проблем (проблемы последовательности, максимальные ящики клубники прибыли), но, похоже, не может найти способ решить эту проблему.

Может кто-нибудь дать некоторые огни о том, как решить эту проблему и/или аналогичные проблемы, которые я могу найти в Интернете или в книге, которая может привести меня к поиску решения DP для этого?

Answer 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.

Если принимаемые вами решения могут быть организованы слева направо поэтапно, где ответ для каждого этапа не зависит от большой информации и может быть рассчитан из ответа на предыдущие этапы, тогда динамическое программирование обычно является практическим способом решения проблемы. Вы можете превратить почти любую проблему в проблему динамического программирования, если вы готовы хранить и вычислять для очень большого количества возможностей на каждом этапе, но в конечном итоге это число становится настолько большим, что так называемое решение становится довольно непрактичным.

В качестве примера, в задаче в верхней части второй стадией является следующая проблема только с двумя ролями, А и В.

[3, 7] → Роль

[1, 5 ] → Роль B

В оригинальной задаче вам необходимо определить общее количество различных команд, если P = 8, то есть если у вас в команде 8 игроков. Проблема второго этапа заключается в том, чтобы выработать количество образований, если есть только две роли, но вам нужно выработать количество формаций для 0 игроков, для 1 игрока, для 2 игроков ... до 8 игроков. Затем, когда вы приступите к выработке ответа на третий этап, вы можете сказать, например: «Если я ставлю 3 игрока в роли CI, у вас осталось 5 игроков и две оставшиеся роли, и я могу посмотреть на ответ, который я уже рассчитал для двух- ролевая проблема с 5 игроками, чтобы увидеть, сколько у них образований с 3 игроками в роли C. "