algorithm - 包含从 1 到 N 的所有数字的最小多集

Question

假设我们只有整数，其值在 1 到 N 范围内。接下来我们将它们拆分为 K-element 多集。你如何找到这样的集合，其中包含这些多集的最小数量，而这个多集的总和包含从 1 到 N 的所有数字？如果出现歧义，答案将是任何符合条件的集合(首先找到)。

例如，我们有N = 9，K = 3

(1,2,3)(4,5,6)(7,8,8)(8,7,6)(1,9,2)(4,4,3)

包含从1到9的所有数字的最小多集数等于4，可以是 (1,2,3)(4,5,6)(7,8,8)(1,9,2) 或 (1,2,3)(4,5,6) (8,7,6)(1,9,2)。

找到这样的集合的高效算法有什么想法吗？

附言 写完答案后，我发现了另一个 4 元素集:(4,5,6)(1,9,2)(4,4,3)(7,8,8) 或 (4,5,6)(1,9,2)(4,4,3)(8,7,6) 但正如我所说，找到任何最小集的算法会没事。

Answer 1

你的问题是经典的限制版Set Covering problem , 但仍然很容易证明它是 NP-Hard .

此问题的任何近似技术在这里都是合理的。特别是 greedy solution选择覆盖最多未发现项目的下一个子集 - 尤其是。易于实现。