algorithm - 动态规划找到所有可能的团队组合

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

Valid team formations: [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]

Number of valid Team Formations: 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 种可能的编队，因为我已经通过仅对角色 A 0 进行了一些削减，然后乘以 20，但仍然需要检查 40^19 种不同的组合。

这个问题必须用动态规划来解决。我已经使用 DP 解决了一些问题(序列问题、最大利润草莓箱)，但似乎找不到解决这个问题的方法。

有人可以就如何解决这个问题和/或我可以在网上或书中找到的类似问题给出一些线索，这些问题可以引导我找到 DP 解决方案吗？

Answer 1

动态编程问题通常以您按顺序排列问题的各个部分而告终，这样您就可以从左到右解决它们，在第 n 阶段做足够的工作，以便您可以引用它以获取第 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 人角色 C 有多少阵型。”