寻找满足一定条件的子集

Question

我有几个数字数组（数组的每个元素只能取 0 或 1 的值），像这样

v1: 1; 0; 0; 1; 1; 
v2: 0; 1; 0; 0; 1; 
v3: 1; 1; 0; 1; 0; 
v4: 1; 0; 0; 1; 0; 
v5: 1; 1; 0; 1; 1; 
v6: 1; 1; 0; 1; 1; 

我希望找到子集，这样当数组求和时，得到的数组具有单独的元素，这些元素是 2 的倍数。例如，v1+v2+v3 给出结果数组 2, 2, 0, 2, 2。结果数组可以具有 2 的倍数的任何值。

另一个示例：

v1: 1, 1, 1, 0, 1, 0
v2: 0, 0, 1, 0, 0, 0
v3: 1, 0, 0, 0, 0, 0
v4: 0, 0, 0, 1, 0, 0
v5: 1, 1, 0, 0, 1, 0
v6: 0, 0, 1, 1, 0, 0
v7: 1, 0, 1, 1, 0, 0

在此示例中， v1+v2+v5 和 v3+v6+v7 是合适的答案。

我想到了一个强力解决方案，但我想检查是否有更有效的方法。这相当于子集和问题吗？

Answer 1

您想找到所有解决方案还是一个？

这可以找到一个解决方案（并且我认为可能可以扩展它以找到所有解决方案）。

将每个数组表示为二进制数。

因此 v1 变为 10011，v2 变为 01001 等等。

令 * 表示按位 mod 2 加法。

例如

v1*v2*v3 = 00000

，我们的目标是找到 mod 2 加法全为零的数组。
设 u 和 v 为任意二进制数。
那么 u*v = 0 iff u = v。

例如

(v1*v2)*v3 = 0
v1*v2 = 11010 = v3.

，如果 u*v = w

u*v*v = w*v, so
u*0 = w*v,
u = w*v

那么我们可以从 0 开始进行反向搜索。假设最终的数组集合包含 v。那么 v*T = 0，其中 T 是一些二进制数。我们有 T = 0*v。如果 T 是给定数组之一，那么我们就完成了。否则我们从 T 开始继续搜索。

这在下面正式描述。

每个状态都是一个二进制数。

设 0 为初始状态。

给定的数组是状态空间的某个子集，比如 S。

我们的目标状态是 S 中的任何元素。

令 T 为所需的数组子集，其总和为 0。

在每个状态下，让可能的操作为 *，其中任何状态不在T.

在每个动作之后放入 T 中使用的数组。

如果在任何非目标阶段 S = T，则无解。

现在我们可以在这个空间上运行 DFS 来寻找解决方案。