数组分区

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

你描述的问题被称为最大集合打包:给定一个集合(你的数组)和一组子集(你的请求)，找出没有共同元素的子集(请求)的最大数量(成对不相交)

如维基百科文章所示，该问题可以表示为一个整数线性规划，可以用标准求解器求解。因为这些都是高度优化的，所以这是你可能得到的最优值。像许多打包问题一样，这个问题是np困难的，所以如果你试图自己实现它，你不能做得比暴力破解更好。