python - 如何为 2 支球队相互比赛找到最佳解决方案？

Question

我得到了一张 A 队和 B 队的表格，其中每对 2 名球员都有编号。行代表A队球员，列代表B队球员。如果数字为正，则表示球员A优​​于B队球员，如果为负，则反之。

例如:

-710 415 527 -641 175 48
-447 -799 253 626 304 895
509 -523 -758 -678 -689 92
24 -318 -61 -9 174 255
487 408 696 861 -394 -67

两队都知道这张 table 。 现在，做的是A队上报5名球员，B队可以看一下，为他们选出最好的5名球员。 如果我们想对球队进行统计，我们会从表格中总结给定位置上的数字，知道每个球队都有一个被计算两次的队长(就好像一个球队有 6 名球员并且队长在那里两次)，如果总和是积极的，A队更好。

输入是数字a(行数/玩家A)和b(列数/玩家B)和这样的表格:

6
6
-54 -927 428 -510 911 93
-710 415 527 -641 175 48
-447 -799 253 626 304 895
509 -523 -758 -678 -689 92
24 -318 -61 -9 174 255
487 408 696 861 -394 -67

输出应该是1282。

所以，我所做的是将数字放入这样的矩阵中:

a, b = int(input()), int(input())

matrix = [list(map(int,input().split())) for _ in range(a)]

我为此使用了 MinHeap 和 MaxHeap。我将这些行放入 MaxHeap 中，因为 A 队想要最大的，然后我从中得到 5 个最好的 A 球员，如下所示:

for player, values in enumerate(matrix):
    maxheap.enqueue(sum(values), player)

playersA = []
overallA = 0

for i in range(5):
    ov, pl  = maxheap.remove_max()
    if i == 0: # it is a captain
        playersA.append(pl)
        overallA += ov
        
    playersA.append(pl)
    overallA += ov

B 队知道 A 球员，使用 MinHeap 找到最好的 5 名球员:

for i in range(b):
    player = []
    ov = 0
    for j in range(a): #take out a column of a matrix
        player.append(matrix[j][i])


    for rival in playersA: #counting only players already chosen by A
        ov += player[rival]

    minheap.enqueue(ov,i)

playersB = []
overallB = 0

for i in range(5):
    ov, pl = minheap.remove_min()
    if i == 0:
        playersB.append(pl)
        overallB += ov
        
    playersB.append(pl)
    overallB += ov

有了玩家，然后我从矩阵中计算总和:

out = 0
for a in playersA:
    for b in playersB:
        out += matrix[a][b]
print(out)

但是，此解决方案并不总是提供正确的解决方案。例如，它用于输入:

10
10
-802 -781 826 997 -403 243 -533 -694 195 182
103 182 -14 130 953 -900 43 334 -724 716
-350 506 184 691 -785 742 -303 -682 186 -520
25 -815 475 -407 -78 509 -512 714 898 243
758 -743 -504 -160 855 -792 -177 747 188 -190
333 -439 529 795 -500 112 625 -2 -994 282
824 498 -899 158 453 644 117 598 432 310
-799 594 933 -15 47 -687 68 480 -933 -631
741 400 979 -52 -78 -744 -573 -170 882 -610
-376 -928 -324 658 -538 811 -724 848 344 -308

但这不是为了

11
11
279 475 -894 -641 -716 687 253 -451 580 -727 -509
880 -778 -867 -527 816 -458 -136 -517 217 58 740
360 -841 492 -3 940 754 -584 715 -389 438 -887
-739 664 972 838 -974 -802 799 258 628 3 815
952 -404 -273 -323 -948 674 687 233 62 -339 352
285 -535 -812 -452 -335 -452 -799 -902 691 195 -837
-78 56 459 -178 631 -348 481 608 -131 -575 732
-212 -826 -547 440 -399 -994 486 -382 -509 483 -786
-94 -983 785 -8 445 -462 -138 804 749 890 -890
-184 872 -341 776 447 -573 405 462 -76 -69 906
-617 704 292 287 464 -711 354 428 444 -42 45

所以问题是:是否可以这样做，或者是否有另一种快速算法( O(n ** 2 )/O(n ** 3) 等)，或者我只是尝试了所有可能的组合在 O(n!) 时间复杂度内使用蛮力？

Answer 1

有一种方法可以用多项式复杂度来做到这一点。

为了向您展示您的解决方案为何不起作用，让我们考虑另一个更简单的问题。假设每支球队只选择 2 名球员并且没有队长。

我们还采用一个简单的分数矩阵:

1 1 1 2 1
1 1 1 1 1
0 3 0 2 0
0 0 0 0 4
0 0 0 0 4

在这里你可以看到 A 队没有机会获胜(因为没有负数)，但他们仍然会尽力而为。他们应该选择谁？

使用您的算法，A 队应该选出他们最好的球员，他们的排名将是:

pa0 < pa1 = pa2 < pa3 = pa4

如果他们选择 pa3 和 pa4，他们都是 4 分(这很糟糕，但没有 pa0 的 6 分那么糟糕)，B 队将以 8 分获胜(他们将选择 pb4 和另一个没有得分的球员没关系)。

另一方面，如果 A 队选择 pa0 和 pa1(根据您的指标，他们比 pa3 和 pa4 差)，B 队能获得的最好成绩是赢 5(如果他们选择 pb3 和任何其他球员)

基本上，您的近似没有考虑到 B 队只能选择两名球员，因此无法利用 pa0+pa1 的弱点，而它可以轻松利用 pa3+pa4 的弱点。

更好的解决方案是 A 队仅通过考虑他们的 2 个最差分数(如果要选择 5 个球员，则为 5 个)来评估每个球员的分数:这将使排名如下:

pa2 < pa3 = pa4 < pa0 < pa1

这仍然是一个近似值:一些组合，如 pa2+pa3 实际上并不像听起来那么糟糕，再次，弱点分布得足够多，B 队无法利用它们(尽管对于这个例子近似值会产生最佳结果)。

我们真正需要选择的不是两个最好的玩家，而是两个玩家的最佳组合，遗憾的是除了尝试所有 $s!/(k!(s-k)!) $ s 中 k 名球员的组合(球队的规模)。不过，还不错，对于 k=2 来说只有 $s*(s-1)/2$ 而对于 k=5 那就是 $s*(s-1)(s-2)(s-3)*(s-4)/5!$，尽管在 O(s^5) 中，它在复杂度上仍然是多项式。将船长添加到组合中只会使组合数乘以 k。它还需要改变如何计算分数，但您应该能够找到它。

既然 A 队已经选择了他们的球员，B 队就可以轻松地选择他们的球员了。这要简单得多，因为每个玩家都可以单独选择。

---

最后一个算法应如何与开头提供的分数矩阵一起工作的示例。

A队有10种可能的组合:pa0+pa1、pa0+pa2、pa0+pa3、pa0+pa4、pa1+pa2、pa1+pa3、pa1+pa4、pa2+pa3、pa2+pa4、pa3+pa4。他们各自的分数是:5, 8, 7, 7, 7, 6, 6, 7, 7, 8。

最佳组合是 pa0+pa1，因此他们将其发送给 B 队。

B 队计算每个球员对 pa0+pa1 的得分:pb0:2、pb1:2、pb2:2、pb3:3、pb4:2。 pb3最好，其他都相等，因此B队派出pb3+pb4(例如)，“答案”为5。