2

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

前任。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}

谢谢

4

1 回答 1

1

不幸的是，受约束的k 子集问题是一个难题……如果你想生成所有这样的 k 子集，你别无选择，只能评估许多可能的候选者。

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

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）来执行子集选择搜索。但是，如果您这样做，请记住在返回结果时将结果子集缩小相同的偏移量。

于 2010-10-05T18:35:36.463 回答