arrays - 数组分区

Question

我有一组对象，编号从 1 到 n，每个对象只有一个实例。现在说，我收到了 k 个请求，每个请求都是为了获取一组对象。那么我应该如何处理这些请求，以便我们可以处理最大数量的请求。我们事先了解所有请求。

---

例如:假设我们有 10 个编号为 1 到 10 的苹果和三个请求:

request 1: {2,6}

request 2: {1,2,3,4,5}

request 3: {6,7,8,9,10}

所以在这里，如果我们处理请求 1，那么我们只能填满 1 个请求，但如果我们处理 2 和 3，我们可以填满 2 个请求。请建议优化算法。

Answer 1

您描述的问题称为maximum set packing : 给定一个集合(您的数组)和一组子集(您的请求)，找到没有共同元素(成对不相交)的子集(请求)的最大数量。

如wikipedia article所示，问题可以表述为整数线性规划，可以通过标准求解器求解。由于这些都是高度优化的，因此这是您可能获得的最佳选择。与许多打包问题一样，该问题是 NP-hard 问题，因此如果您尝试自己实现此问题，您将无法比蛮力法做得更好。