算法——基于寻找最大匹配数

Question

我遇到了一个问题，但我仍然不知道如何解决。我想出了如何用蛮力的方式来做到这一点，但是当有成千上万的元素时它就不起作用了。

Problem: 
Say you are given the following input:
T F T F T F
T T F T T F
T F F T T T
F T F F T T
T F F T T T

You can inverse columns such as:
T         F
F         T
T   -->   F
F         T
T         F

并且您想找到在给定输入“二维表”的情况下可以获得的最大匹配数，这样匹配意味着具有相同元素的行。你只允许反转列，你可以反转任意多的列，但你只需要找到你能得到的最多匹配项。例如:

T F T
F T F     has only one match "T T T", but if we invert column 1 and 3 it 
T T T     becomes

F F F
T T T     which has two matches "F F F" and "T T T", which is the most 
F T F     number of matches possible for that table.

此外，列数和行数可以是小于 100,000 的任意数字。您将如何有效地做到这一点？

Answer 1

也许我遗漏了什么，但快速浏览一下行应该可以回答您的问题。

从顶行开始，根据需要翻转每一列，直到顶行都是 T。计算匹配项的数量。每隔一行重复一次，看看计数是否大于任何前一行。

您不需要反转整个矩阵，所以每一行都是 F，计数将相同。