我会尽量做到彻底:
- 我有 11 个小组。
- 我有很多人需要在这些组之间进行划分
- 每个人都有一个加权偏好列表。通常在该列表上有 3 个有序的组，但一些异常值会有更多或更少的组。 IE: 人 1 有进入 A 组的偏好。如果那不可用，她想进入 D 组，如果那个不可用，她想进入 C 组。 人 2 对任何群体都没有偏好。 第 3 个人仅适用于 D 组。
- 组有最大数量。人数多少取决于参与人数，但团体必须保持平衡。
- 理想的群体分配是实现最大偏好的分配。
到目前为止，我知道我需要加权偏好。 3, 2 1 对于怀特来说是一个好的开始。理想的群体分布是，加入该群体的人的偏好总和与加入其他群体的人的偏好总和尽可能接近。
没有偏好意味着所有组的权重为 3。至少在我对其进行微调之前是这样。
不过，我不知道如何编写一个算法来真正开始对其进行排序。帮助？
最佳答案
这看起来像一个 weighted bipartite graph matching problem *，其中一组顶点代表组，另一组顶点代表人，边的权重为 0(如果分配不可能)，或 10/[偏好数量] x [数量preferences - preference number + 1] 或类似的东西(所以如果用户有 5 个偏好，他们的最高偏好权重为 10，接下来是 8，然后是 6，然后是 4，然后是 2)
您可以克隆组顶点以满足分区要求(例如，如果一个组最多可容纳 50 人，则创建该组顶点的 50 个副本)并强制每个顶点一条边，这是很多二分图划分算法旨在处理
二分图匹配(加权和未加权版本)是多项式时间算法
*传统上称为 (stable) marriage problem - 你有一组代表男人的顶点，另一组代表女人的顶点，还有一组(加权的)边表示两组顶点的婚姻偏好
关于algorithm - 排序算法 - 分组，加权，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26001239/