-4

我们正在编写 c# 程序，该程序将帮助我们删除一些不必要的数据重复器，并且已经找到了一些重复器以在查找数组中重叠数据的帮助下删除。现在我们要检查一下，也许我们可以取消其他学期的一些中继器。问题是：

我们有数字数组

{1, 2, 3, 4, 5, 6, 7, ...}, {4, 5, 10, 100}, {100, 1, 20, 50}

有些数字可以在其他数组中重复，有些数字可以是唯一的并且只属于特定的数组。当我们准备从数组中丢失多达 N 个数字时，我们希望删除一些数组。

解释：

  1. {1, 2}

  2. {2, 3, 4, 5}

  3. {2, 7}

我们准备从这些数组中丢失最多 3 个数字，这意味着我们可以删除数组 1，因为我们只会丢失数字“1”，它是唯一的数字。我们也可以删除数组 1 和 3，因为我们将丢失数字“1”、“7”或数组 3，因为我们将只丢失数字“7”并且它少于 3 个数字。

在我们的输出中，我们想要给出可以删除的最大数组数量，条件是我们将丢失少于 N 的条件，其中 N 是我们准备丢失的项目数。

4

2 回答 2

1

这个问题等价于Set Cover 问题（例如：取 N=0），因此一般情况下有效、精确的解决方案不太可能。然而，在实践中，启发式和近似通常已经足够好了。鉴于您的问题与 Set Cover 的相似性，贪婪启发式是一个自然的起点。不要在覆盖所有元素时停止，而是在覆盖除 N 个元素之外的所有元素时停止。

于 2014-12-18T02:12:07.133 回答
0

您需要首先为每个数组获取一个数字，该数字告诉您有多少个数字对于该特定数组是唯一的。
一个简单的方法是O(n²)，对于每个元素，您需要检查所有数组是否是唯一的。
通过对数组进行排序、先排序或使用类似堆的数据结构，您可以更有效地做到这一点。

之后，您只需找到一个总和，以便一定数量的数组的数字总和为N。
这类似于子集和问题，但复杂性要小得多，因为N > 0您的所有数字都是> 0.
因此，您只需将这些数字从最小到最大排序，然后遍历排序后的数组并取与 sum 一样长的数字< N。
最后，您可以删除与您能够放入的数字相对应的每个数组N。

于 2014-12-14T22:07:28.830 回答