c - 寻找满足特定条件的子集

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 等等

令 * 表示按位模 2 加法。

例如

v1*v2*v3 = 00000

所以我们的目标是找到模 2 加法全为零的数组。 令 u 和 v 为任意二进制数。 则 u*v = 0 当且仅当 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 的所需数组子集。

在每个状态下，让可能的 Action 是 * 任何不在 T 中的状态。

在每个 Action 之后将使用的数组放入 T。

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

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