Select满足此条件的最大行数
Select maximum number of rows meeting this condition
我在编码竞赛中遇到了这个问题，归结为以下问题：
可以从二进制矩阵中选择的最大行数是多少，使得没有两行的列 AND 非零。 （行的所有对都应具有列方向和零）。
限制条件：行数<=50，列数<=20
例如
00101101
10110001
10000010
答案是 2，（第一行和第三行）。
我可以计算出列数中有一些指数算法（由于限制）。我只是无法找到解决方案。我的所有其他尝试都太复杂了，无法创建图表并找到独立集，而且这些尝试的行数也是指数级的。有人可以帮我解决这个问题吗？
赛后我试着查看其他参赛者的代码，他们似乎是用DP解决的。我不要求完整的解决方案。如果能提供一些详细的提示，我将不胜感激。
编辑：
如果描述不清楚，所选行不应在同一列中有相同的行（抱歉，如果仍然不清楚）。就像在给定的例子中一样，第一行和第二行不能被选择，因为它们在第三和第八列中有一个。同样，无法选择第 2 行和第 3 行，因为它们在第 1 列中有共同的行。第一行和第三行没有共同点。
这是NP难集打包问题。预期的 O(m 2^n) 时间解决方案（其中 m 是行数，n 是列数，小于单词大小）准备一个由 0..m 乘以 0 索引的 table。 .2^n-1，其中单元格 (i, j) 是索引从 0..i 开始的最大行数，其成对 intersections/ANDs 是 empty/zero 并且其 union/OR 是 j。
https://en.wikipedia.org/wiki/Set_packing 给出了确定是否存在 k 个子集的等效问题，从 N 个元素的通用集合的给定子集的集合中，使得 none 个选择的 k 个子集相交.如果决策问题可以在多项式时间内解决，则最大化问题很明显并且可以在多项式时间内解决：最大化问题要求最大 k 使得可以找到 k 个子集，使得 k 个子集中的 none 相交.
不幸的是，这些问题是 NP 难的（具体来说，特定 k 的决策问题是 NP 完全的），因此除非 P = NP，否则没有针对您的问题的通用快速解决方案。也许鉴于您的问题中的行数和列数较少，可以设计 "fast enough" 解决方案。然而，根据我对经典集合打包问题的初步阅读，尚不清楚这样的解决方案是如何工作的。
我在编码竞赛中遇到了这个问题，归结为以下问题：
可以从二进制矩阵中选择的最大行数是多少，使得没有两行的列 AND 非零。 （行的所有对都应具有列方向和零）。
限制条件：行数<=50，列数<=20
例如
00101101
10110001
10000010
答案是 2，（第一行和第三行）。
我可以计算出列数中有一些指数算法（由于限制）。我只是无法找到解决方案。我的所有其他尝试都太复杂了，无法创建图表并找到独立集，而且这些尝试的行数也是指数级的。有人可以帮我解决这个问题吗？
赛后我试着查看其他参赛者的代码，他们似乎是用DP解决的。我不要求完整的解决方案。如果能提供一些详细的提示，我将不胜感激。
编辑：
如果描述不清楚，所选行不应在同一列中有相同的行（抱歉，如果仍然不清楚）。就像在给定的例子中一样，第一行和第二行不能被选择，因为它们在第三和第八列中有一个。同样，无法选择第 2 行和第 3 行，因为它们在第 1 列中有共同的行。第一行和第三行没有共同点。
这是NP难集打包问题。预期的 O(m 2^n) 时间解决方案（其中 m 是行数，n 是列数，小于单词大小）准备一个由 0..m 乘以 0 索引的 table。 .2^n-1，其中单元格 (i, j) 是索引从 0..i 开始的最大行数，其成对 intersections/ANDs 是 empty/zero 并且其 union/OR 是 j。
https://en.wikipedia.org/wiki/Set_packing 给出了确定是否存在 k 个子集的等效问题，从 N 个元素的通用集合的给定子集的集合中，使得 none 个选择的 k 个子集相交.如果决策问题可以在多项式时间内解决，则最大化问题很明显并且可以在多项式时间内解决：最大化问题要求最大 k 使得可以找到 k 个子集，使得 k 个子集中的 none 相交.
不幸的是，这些问题是 NP 难的（具体来说，特定 k 的决策问题是 NP 完全的），因此除非 P = NP，否则没有针对您的问题的通用快速解决方案。也许鉴于您的问题中的行数和列数较少，可以设计 "fast enough" 解决方案。然而，根据我对经典集合打包问题的初步阅读，尚不清楚这样的解决方案是如何工作的。