c++ - 编程中这两个任务中的任何一个都有算法方法吗？

Question

我正在做数学研究，我需要执行以下任务：

给定一组未指定的向量，确定哪些向量可以求和为恒等向量 (1, 1, ..., 1)

例如，考虑向量

x1 = (1 0 0)
x2 = (0 1 1)
x3 = (1 0 0)

如果将向量 x1 和 x2 相加，则得到(1, 1, 1).

或者举一个更大的例子

x1 = (1 0 0 0)
x2 = (0 1 1 0)
x3 = (0 0 1 1)
x4 = (0 0 0 1)

如果将向量 1、2 和 4 相加，则得到(1, 1, 1, 1).

我需要一种通常可以做到这一点的算法。

第二个任务......给定一组未指定的数字，确定哪些总和为 1。

例如：

x1 = 0.2
x2 = 0.5
x3 = 0.6
x4 = 0.4
x5 = 0.3
x6 = 0.1
x1 + x2 + x5 = 0.2 + 0.5 + 0.3 = 1

但是也，x1 + x4 + x5 + x6 = 1

我需要能够对计算机进行编程以完成上述任务之一以进一步研究。

Answer 1

对于第一个任务，它是子集和问题的变体，可以通过动态规划来解决。子集和问题与您的问题之间的区别在于子集和问题只有一维。在您的情况下，您需要扩展其动态编程方法以处理多个维度。

对于您的第二个任务，它与子集和问题相同。

Answer 2

是的，研究...

如何从蛮力开始：创建集合的所有 2^N 个子集，并为每个这样的候选者求和，如果它与目标匹配，则存储它。