algorithm - 等k子集算法

Question

有谁知道等 k 子集算法的良好且高效的算法？最好是 c 或 c++，它可以处理 100 个元素的向量，可能具有复杂性和时间估计

例如。 9元向量

x = {2,4,5,6,8,9,11,13,14}

我需要生成总和 = 24 的所有 k=3 个不相交的子集该算法应该检查是否有 k 个不相交的子集，每个子​​集的元素总和为 24，并按升序(在子集中和子集之间)列出它们，或者查看解决方案是否不存在

解决方案

解决方案 1:{2 8 14} {4 9 11} {5 6 13}

解决方案 2:{2 9 13} {4 6 14} {5 8 11}

谢谢

Answer 1

不幸的是约束k-subset problem is a hard problem ...如果你想生成所有这样的k子集，你别无选择，只能evaluate many possible candidates .

您可以执行一些优化来减少搜索空间。

给定一个包含整数值的域x，给定一个正整数目标 M，给定子集的正整数 k 大小，

1. 当 x 仅包含正整数并给定上限 M 时，从 x 中删除所有大于或等于 M 的项目。这些项目不可能是子集的一部分。
2. 类似地，对于 k > 1、给定的 M 和包含正整数的 x，从 x 中删除所有大于 M + min0 + min1 ... minK 的项目。从本质上讲，删除所有不可能成为子集一部分的大值，因为即使选择小值，它们也会导致总和超过 M。
3. 您还可以使用偶数/奇数排除原则来缩减搜索空间。例如，k 是奇数，M 是偶数，您知道总和将包含三个偶数或两个奇数和一个偶数。您可以使用此信息来减少搜索空间，方法是从 x 中消除可能属于总和的候选值。
4. 对向量 x 进行排序 - 这使您可以快速排除不可能包含在总和中的值。

当向量 x 包含负值时，其中许多优化(除了偶数/奇数排除)不再有用/有效。在这种情况下，您几乎必须进行详尽搜索。

正如 Jilles De Wit 指出的，如果 X 包含负数，您可以将 X 中最小值的绝对值添加到 X 的每个成员。这会将所有值移回正数范围 -使我上面描述的一些优化再次成为可能。但是，这要求您能够准确地表示放大范围内的正值。实现此目的的一种方法是在内部使用更广泛的类型(比如 long 而不是 int)来执行子集选择搜索。但是，如果您这样做，请记住在返回结果时将结果子集按相同的偏移量缩小。