2

我有一个列表，其成员是从整数 1 到 600 [或出于存储目的从 0 到 599] 中选择的 5 个数字的集合。我需要选择此列表的子列表，以便在此子列表中的集合中，1 到 600 范围内的每个整数只出现一次，因此是 120 个元素的子列表。我的列表中包含 4200 或 840 个元素——我将通过运行来确定是否需要更大的数字。我需要任何一个这样的子列表。

这对我来说听起来像是一个标准问题，但我不知道如何搜索。有人可以帮忙提供算法吗？

4

1 回答 1

1

从设置封面问题

集合覆盖的贪心算法根据一个规则选择集合：在每个阶段，选择包含最多未覆盖元素的集合

维基百科似乎说这种算法在合理的复杂性假设下效果最好。

我会将其归结为以下步骤：

  1. 从列表中选择一个元素（可能是第一个）
  2. 选择您遇到的下一个元素，其中所有 5 个数字尚未在子列表中表示
  3. 如果您到达末尾，请返回列表的开头并将步骤＃2 的标准降低到 4 个数字
  4. 重复第 2 步和第 3 步，直到你覆盖了所有整数

根据您使用的编程语言，有一些方法可以快速完成。

编辑：张贴者解释说每个整数必须只使用一次

所以，你真正需要做的只是继续添加元素，直到元素包含一个已经存在于你的子集中的整数。“完全”标准优先于“尚未在子集中”标准。当您达到 120 个子集时，您将跳出循环。

您可能还想跟踪将元素添加到子集中的顺序，并且当您遇到死胡同时（例如，超集中剩余的每个元素都包含一个已经存在于您的子集中的整数），您回溯一个元素并继续。

为了回溯并记住哪些组合不起作用，您需要保留一个“禁止集合”列表，并且每次决定是否添加新元素时，您首先应确保它不在此禁止集合列表中。在 Ruby 中执行此操作的最佳方法（我发现）是存储集合的哈希而不是集合本身。这提供了一种廉价的方式来评估预期的收集是否已经尝试过并导致了死胡同。

祝你好运！

于 2013-09-07T17:48:46.503 回答