嗨，我正在建立一个项目，学生们报名参加在全国几个城市举行的考试。在报名时，学生们根据自己的喜好提供了三个他们想要参加考试的城市名单。因此，一个学生可能会说他对考试中心的第一选择是纽约，其次是芝加哥，最后是波士顿。
现在请记住，由于考试中心的容量有限，他们不能容纳每个学生的第一选择。然而，我们会尽力为尽可能多的学生提供他们的第一或第二选择中心，并尽可能避免学生不得不把第三选择中心给学生
现在有什么排序算法可以使这个过程更有效吗?最简单的方法是首先浏览第一选择的学生名单，尽可能多地分配，然后再浏览第二选择的学生名单，然后再分配。然而，这可能会导致名单上第一名的学生得到他们的第一个中心，最后一名学生得到他们的第三个选择，甚至更糟的是没有选择。任何能让这更有效率的方法
听起来像是经典的稳定婚姻问题或大学入学问题的变体。维基百科列出了前者的线性时间算法(在偏好数量上，O(n²)在人数上);对于后者，NRMP描述了一个有效的算法。
我怀疑，如果你随机为学生生成考试地点的偏好(每个考试地点一个Fisher-Yates洗牌)，然后应用稳定婚姻算法，你会得到一个相当公平和有效的解决方案。
这个问题可以表示为最小成本流的一个实例。设N为学生人数。设每个学生是一个容量为1的源顶点。设每个考试中心是一个有容量的汇聚点，好吧，它的容量。从每个学生到他的第一、第二和第三个选择画一个弧线。将第一选择弧线的代价设为0;第二选择的成本趋于1;第三种选择的成本为N + 1。
找到移动N个单位流量的最小成本流。假设你的解算器返回一个积分解(它应该;流动lp是完全单模的)，每个学生流动一个单元到他指定的中心。成本使第三种选择的作业数量最小化，通过第二种选择的作业数量打破了关系。
有一类算法处理这种有限资源的分配，称为拍卖。基本上在这种情况下，每个学生都会得到一定数量的钱(一个他们可以花的数字)，然后你的软件会在这些学生之间进行竞标。您可以使用基于首选项的公式。
教程时间就是一个例子。如果你写下你的偏好，那么你就会在那些时间出价更高，而在你不想要的时间出价更低。所以如果你没有得到你的偏好，你就有更多的"钱"来竞标其他教程。