algorithm - Sort object pairs into separate bins

Question

I have N object pairs (master copy/slave copy) all with the same size. I wish to distribute the copies among M bins each with a different capacity so that no bin will include both the master and slave copy.

What's the most efficient algorithm? And more importantly what's the most efficient algorithm to find out if there is a possible solution for a given input (without actually generating the solution)?

Answer 1

很难想象有比蛮力更好的方法：通过递减剩余容量来跟踪优先队列中的 M 个 bin，并将每个对象对添加到队列中的前两个 bin；重新平衡队列并重复。如果 M 个 bin 的总容量 >= 2*N，则存在解决方案。

这似乎是复杂度 O(N * log M)

注意：对于恰好三个箱，不存在 N > M1 + M2 的解决方案，其中 Mn 是箱 n 的容量，按 n 在 0..M 范围内的容量降序排序，与 M0 的容量无关。

同样对于恰好 2 个 bin，解决方案仅存在于 N <= M1。

Answer 2

一个简单的解决方案是：

将 M 个桶按照容量降序排列：x1, x2,..,xm

选择最上面的两个桶，为该对分配一个对象，减少两个桶的可用容量并重新排列桶。您可以使用堆来跟踪存储桶，复杂度接近 O(n)

不断重复，直到所有对象都分配完毕。