algorithm - 将元素分配到有条件的 bin 中

Question

给定一个集合

struct Person {
    string name;
    int team;
    bool swimmer;
};

vector<Person> people;

是否有一种“众所周知的”算法可以将它们分配到具有以下条件的最少数量的固定大小的 bin 中：

1. 同一个垃圾箱中的两个人不能来自同一个团队
2. 每个垃圾箱中至少有一个人必须是游泳者

我正在寻找一种解决方案，该解决方案具有容纳每个人所需的最少垃圾箱数量。垃圾箱不必完全装满。

如果一半是游泳者并且垃圾箱大小为四个，最简单的解决方案是将一名游泳者与一名非游泳者放在一起。然而，最有效的解决方案是将两名游泳者和两名非游泳者放在一个垃圾箱中（团队成员允许）。

不同团队的数量可能大于一个垃圾箱的大小，因此会有很多解决方案。

显然，如果people.size() / bin_size > number of swimmers，将没有解决方案。

标签： algorithm

Answer 1

它似乎是装箱问题的变体。

这是一个 NP 完全问题，但文献中有很多算法可以解决它，包括在线和离线方法。

在您的情况下，您事先知道数据，因此您可能需要首次拟合递减 (FFD) 算法或其修改版本，它最多在O(nlog(n)).

您必须修改标准算法以引入约束。