程序员经验分享-hwhale

基于偏好的分组算法

2024-03-04

我正在寻找一种方法来根据偏好将人们分类。

例如，假设有 100 名学生，每人将被分配到以下五个班级之一：

  • 科学 - 40 个座位
  • 数学 - 15 个席位
  • 历史 - 15 个席位
  • 电脑 - 20 个座位
  • 写作 - 10 个座位

每个学生都有三个按偏好排序的首选课程。划分学生的最佳方法是什么，以便尽可能多的人获得第一和第二选择的班级，同时确保没有班级的房间里有太多的学生。

我考虑过通过以下方法来处理它：

  1. 按首选班级对所有学生进行分组
  2. 查看哪些班级学生太多，哪些班级学生太少
  3. 检查超额预订班级中是否有学生有预订不足的第二选择课程
  4. 相应地移动这些学生
  5. 对第三选择课程重复 2-4

虽然我觉得这是一个合理的实现，但我想知道是否有其他算法可以更好地解决这个问题。我尝试到处搜索，但找不到任何可以解决此类问题的方法。


从你的描述来看，这听起来很像稳定的婚姻问题 http://en.wikipedia.org/wiki/Stable_marriage_problem

检查 Wiki 链接，您将看到 Gale-Shapley 算法的描述，这是一个很好的解决方案。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

set

GROUPING

preferences

基于偏好的分组算法 的相关文章

  • 在无向图中查找强连通分量

    我想在无向图中找到强连接的组件 即如果我从节点开始A然后我会回到节点A并且每条边都被恰好访问一次 对于有向图可以使用Tarjan算法来寻找强连通分量 但是对于无向图怎么办 我认为您错过了强连通分量的含义 强连接组件 如果所有顶点对之间都存在

  • 哪种数据聚类算法适合检测时间序列事件中未知数量的聚类？

    这是我的场景 考虑在不同地点和时间发生的一组事件 例如 考虑有人在高空记录暴风雨期间城市中的雷击 就我的目的而言 闪电是瞬时的 只能击中某些位置 例如高层建筑 还可以想象每次雷击都有一个唯一的 ID 以便以后可以参考该雷击 这个城市大约有1

  • 按百分比减少多边形面积

    我有一个由点 x y 组成的多边形 我想做的是将其减少一个百分比 请记住 我不想只是扩大规模 多边形应该有一种内部边界 其宽度取决于百分比 该内部边界被多边形切断 谁知道可以实现这一目标的算法 输入 点数组 百分比 输出 点数组 你所寻求的

  • 使到 n 个点的集合的欧氏距离之和最小的点

    我有一组点W x1 y1 x2 y2 xn yn 在 2D 平面上 你能找到一种算法 将这些点作为输入并返回一个点 x y 在 2D 平面上 距以下点的距离之和最小W 换句话说 如果 di Euclidean distance x y xi

  • C 中的菱形数组排序

    我有以下 C 语言作业 我基本上需要一种方法而不是解决方案 我们有一个 13 x 13 的数组 在数组中 我们有一个需要考虑的菱形形状 该菱形之外的所有内容都初始化为 1 不重要 下面的 5 x 5 数组示例 x x 1 x x x 2 2

  • 如何在给定目标索引数组的情况下对数组进行就地排序？

    你如何对给定的数组进行排序arr in place给定目标索引数组ind 例如 var arr A B C D E F var ind 4 0 5 2 1 3 rearrange arr ind console log arr gt B E

  • 在 O(n) 时间内找到 n x n 矩阵中的局部最小值

    所以 这不是我的家庭作业问题 而是取自 coursera 算法和数据结构课程的未评分作业 现已完成 You are given an n by n grid of distinct numbers A number is a local m

  • Ruby 中的 Set 是否始终保留插入顺序？

    即 Ruby 的 Set 相当于 Java 的 LinkedHashSet 吗 在 Ruby 1 9 中 yes 在 Ruby 1 8 中 可能不会 Set uses a Hash内部 https github com ruby ruby

  • 通过分布式数据库聚合作业优化网络带宽

    我有一个分布式 联合数据库 结构如下 数据库分布在三个地理位置 节点 每个节点集群有多个数据库 关系数据库是 PostgreSQL MySQL Oracle 和 MS SQL Server 的混合体 非关系数据库是 MongoDB 或 Ca

  • 确定解决迷宫问题的最小线段数

    我有一个问题 我需要定义一个具有最少数量的顶点的多边形 该多边形与不透明的图像中的每个像素相交或包含每个像素 令 N 为图像中的像素数 我唯一的假设是图像的边界 孔 内不能包含透明像素 并且至少有两个像素是不透明的 举个例子 假设我有以下图

  • 检索受“rowspan”影响的行的列索引的最有效方法是什么？

    考虑下表 table thead tr th th th A th th B th th C th tr thead tbody tr th 1 th td Apples td td Oranges td td Pears td tr tb

  • 如何从一组重叠的圆计算多边形集？

    这个问题是一些计算细节的扩展这个问题 https stackoverflow com questions 1667310 combined area of overlapping circles 假设有一组 可能重叠的 圆 并且希望计算这组

  • 如何将无向图转换为 DAG？

    The 维基页面 http en wikipedia org wiki Directed acyclic graph Relation to other kinds of graphs says 任何无向图都可以通过为其顶点选择总顺序并将每

  • 高维最近邻搜索的最佳数据结构

    我实际上正在处理高维数据 50 000 100 000 个特征 并且必须对其执行最近邻搜索 我知道随着维度的增长 KD 树的性能很差 而且我还了解到 一般来说 所有空间分区数据结构都倾向于对高维数据执行详尽的搜索 此外 还有两个重要事实需要

  • 固定大小集以包含给定集的最大数量

    我有大约 1000 组尺寸 1 4 1 3 3 5 6 4 5 6 7 5 25 42 67 100 是否有可能找到包含最大数量的给定集合的大小为 20 的集合 检查每一个100 80 20 集 效率低下 我不太确定这是 NP 完全的 考虑

  • 如何确定算法函数的复杂度？

    您如何知道算法函数对于特定操作是否需要线性 常数 对数时间 它取决于CPU周期吗 您可以通过三种方式 至少 做到这一点 在网上查找算法 看看它是如何描述其时间复杂度的 根据输入大小 自己检查算法 查看嵌套循环和递归条件等内容 以及每个循环运

  • 点集子集的最小周长凸包

    给定平面上的 n 个点 没有 3 个共线 给定数字 k 找到 k 个点的子集 使得 k 个点的凸包在 k 个点的子集的任何凸包中具有最小周长 我可以想到一个简单的方法 运行时间为 O n k k log k 找到大小为 k 的每个子集的凸包

  • 在 C++ 中通过引用传递 std 算法谓词

    我正在尝试从 a 中删除元素std list并保留已删除元素的一些统计信息 为此 我使用列表中的remove if 函数 并且我有一个谓词 我想使用这个谓词来收集统计数据 这是谓词的代码 class TestPredicate privat

  • 7 张牌扑克手牌评估器

    有谁知道评估 7 张牌扑克牌的快速算法吗 这比简单地暴力检查 7 张牌中每 21 个 5 张牌的组合更有效 Cheers Pete 我写了一篇JavaScript 核心评估方法仅使用位操作 因此速度非常快 考虑到这一点 查看 21 种组合还

  • 使用多级解决方案计算二维网格中的最近邻

    我有一个问题 在 x y 大小的网格中 我提供了一个点 并且我需要找到最近的邻居 在实践中 我试图在 pygame 中找到距离光标最近的点 该点跨越颜色距离阈值 计算如下 sqrt rgb1 0 rgb2 0 2 rgb1 1 rgb2 1

随机推荐

热门标签