algorithm - 选择满足此条件的最大行数

Question

我在编码竞赛中遇到了这个问题，归结为以下问题:

可以从二进制矩阵中选择的最大行数是多少，使得没有两行的列 AND 非零。 (行的所有对都应具有列方向和零)。

约束:行<=50，列<=20

例如。

00101101

10110001

10000010

答案是 2，(第一行和第三行)。

我可以计算出列数中存在某种指数算法(由于约束)。我只是无法找到解决方案。我的所有其他尝试都太复杂了，无法创建图表并找到独立集，而且这些尝试的行数也是指数级的。有人可以帮我解决这个问题吗？

赛后我试着查看其他参赛者的代码，他们似乎是用DP解决的。我不要求完整的解决方案。如果能提供一些详细的提示，我将不胜感激。

编辑:

如果描述不清楚，则所选行不应在同一列中有相同的行(抱歉，如果仍然不清楚)。就像在给定的例子中一样，第一行和第二行不能被选择，因为它们在第三和第八列中有一个。同样，无法选择第 2 行和第 3 行，因为它们在第 1 列中有共同的行。第一行和第三行没有共同点。

Answer 1

这是 NP 难集打包问题。预期的 O(m 2^n) 时间解决方案(其中 m 是行数，n 是列数，小于字大小)准备一个由 0..m 乘以 0..2^n 索引的表-1，其中单元格 (i, j) 是索引从 0..i 开始的最大行数，其成对交集/AND 为空/零且并集/OR 为 j。