0

想象一下，你是一名足球队教练。球场上有11名球员和11个不同的位置。每个玩家都能够在指定位置以特定等级在所有 11 个不同位置上进行比赛。

作为球队的教练，你必须为球队（由所有 11 名球员组成）决定最强的阵容，以使整体评分（即评分总和）最大化。没有两名球员可以在同一个位置上比赛。

例如，考虑一个较小的 LINEUP 问题，其中只有 3 名玩家玩某个游戏。

3 2 1
4 1 5
6 7 3

玩家 1 可以在排名 3 的位置 1、排名 2 的位置 2 和排名 1 的位置 3 上玩。类似地，对于所有玩家，第 i 列代表他们在第 i 位置的排名。最佳阵容是当球员 1 在位置 1、球员 2 在位置 3、球员 3 在位置 2 时，最高评分 = 15 (3 + 5 + 7)。

那么，如何通过动态规划来解决这个问题呢？我在论坛上读到有人通过 DP 解决了这个问题，但我无法弄清楚这个问题是如何拥有最优子结构的。所以请帮我弄清楚....

Plz还提到DP是否可以解决问题

并请适当地编辑标题...

4

2 回答 2

2

我相信你这里有一个分配问题，可以通过匈牙利方法解决。

如果你真的想要一个 DP 解决方案，这里有一个想法。为什么没有F[i,j], i=0..11, j = 0..2^11-1. i- 是您可以选择的球员数量j- 是一个位掩码，表示所覆盖的场地位置，是F您可以获得的最大“团队价值”。例如i = 1，只有那些j二进制表示最多包含一个设置位的值才是“有效的”。显然，你不能只用一名球员来转换多个位置。

// initialize the F[][] array with -infinity
F[0][0] = 0;

for(i = 1; i <= 11; ++1)
{
  for(j = 0; j < 2^11; ++j)
    for(k = 0; k < 11; ++k )
    if( (j & (1 << k)) == 0 ) // k-th position is not occupied?
      F[i][j | (1 << k)] = max( F[i][j | (1 << k)], F[i-1][j] + <value of payer i playing at position k> );
}

ANSWER = F[11][2^11-1]

这显然可以优化：因为F[i]我们只对包含精确i设置位的位掩码感兴趣。

通过用位图表示可能的状态，将组合问题转化为 DP 问题的技术有一个名称，但我不记得了。解决这个问题的正确方法仍然是匈牙利方法。

于 2012-12-27T07:33:26.950 回答
0

这是一个匹配问题。你可以使用KM算法来解决Alex提到的wiki 和匈牙利方法是KM的一个特例。对于 DP 方法，Ales 给出了正确的答案。由于玩家人数不多，这里可以使用位操作的方法

于 2012-12-29T03:01:55.823 回答