算法preference基于分组 [英] Algorithm for preference based grouping
问题描述
我期待想出一个办法由preference人变成类进行排序。
I am looking to figure out a way to sort people into classes by preference.
举例来说，假设有100名学生被每个将要分配五类之一：
For example, say there are 100 students that are each going to be assigned one of five classes:
- 科学 - 40席
- 数学 - 15席
- 历史 - 15席
- 计算机 - 20席
- 写作 - 10席
每个学生都有由preference订购了三preferred类。什么是接近瓜分学生，让尽可能多的人得到他们的第一和第二选择的类成为可能，而在同一时间来确保没有类有太多的学生对于房间的最佳方式。
Each student has three preferred classes that are ordered by preference. What is the best way to approach dividing up the students so that as many people get their first and second choice classes as possible, while at the same time making sure that no class has too many students for the room.
我想过通过以下方法接近它：
I've thought about approaching it by the following method:
- 在集团所有的学生通过他们的第一选择一流
- 查看哪些类有太多的学生和具有太少
- 检查，看是否有学生在超额预订类有这些underbooked中策类
- 将这些学生相应
- 在与第三选择课程重复2-4
虽然我觉得这是一个合理的实现，我想知道是否存在解决一个更好的方法这个问题的任何其他算法。我试图寻找遍，但我找不到任何可以解决这样的问题。
While I feel like this is a reasonable implementation, I am wondering if there are any other algorithms that solve this problem in a better way. I have tried searching all over, but I cannot find anything that would solve this kind of problem.
推荐答案
从你的描述，这听起来非常像的稳定的婚姻问题
From your description, this sounds very much like one of the variations of the Stable Marriage Problem
检查维基链接，你会看到盖尔 - 沙普利算法，这是一个很好的解决方案的说明。
Check the Wiki link and you will see a description of the Gale-Shapley Algorithm, which is a good solution.
这篇关于算法preference基于分组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
