动态规划发现所有可能的团队组合

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是三种类型的角色( 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 <8无效的团队组建

这都是有趣的游戏，直到玩家的数量达到40，而角色的数量达到20，Min =0和Max = 40。

示例：

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

在这种情况下，我需要检查40^20可能的结构，我已经做了一些削减，只为角色A0，然后乘以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球员的答案。

如果您所做的决策可以按阶段从左到右排列，其中每个阶段的答案不依赖于很多信息，并且可以根据前几个阶段的答案计算，那么动态规划通常是解决问题的一种实用方法。你几乎可以将任何问题转化为动态规划问题，如果你准备在每个阶段存储和计算大量的可能性，但最终这个数字变得如此之大，以至于所谓的解决方案变得相当不切实际。

例如，在顶部的问题中，第二阶段是下面的问题，只有两个角色，A和B。

3，7→角色A

1，5→角色B

在最初的问题中，如果是P=8，你需要计算出不同队形的总数，也就是说，如果你有8名队员的话。第二阶段的问题是，如果只有两个角色的话，计算出阵形的数目，但是你需要计算出0、1、2的阵形数。最多有8名选手。然后，当你计算出第三阶段的答案时，你可以说：“如果我让3名玩家进入角色C，我还剩下5名球员，剩下2名角色，我可以看看我已经计算出了5名玩家的双角色问题的答案，看看C角色中有3名球员有多少阵型。”