某运动会设立N个比赛项目,每个运动员可以参加1-3个项目。试问如何安排比赛日程,既可以使,既可以使同一运动员参加的项目不在同一单位时间进行,又使总的竞赛日程最短。(用数据结构的队列解决问题)
1条回答 默认 最新
关注
问题抽象:若将此问题抽象成数学模型,则归属于“划分子集”问题。N个比赛项目构成一个大小为n的集合,有同一运动员参加的项目则抽象为“冲突”关系。
解决问题:假设某运动会设有9个项目,A = {0, 1, 2, 3, 4, 5, 6, 7, 8},7名运动员报名参加的项目分别为:(1, 4, 8)、(1, 7)、(8, 3)、(1, 0, 5)、(3, 4)、(5, 6, 2)和(6, 4),则构成一个冲突关系的集合R = { (1, 4), (4, 8), (1, 8), (1, 7), (8, 3), (1, 0), (0, 5), (1, 5), (3, 4), (5, 6), (5, 2), (6, 2), (6, 4)}(一对括号中的两个项目不能安排在同一单位时间)。“划分子集”问题即将集合A划分成k个互不相交的子集A1, A2, ... , Ak(k <= n),使同一子集中的元素均无冲突关系。
解决 无用评论 打赏 举报
悬赏问题
- ¥200 csgo2的viewmatrix值是否还有别的获取方式
- ¥15 Stable Diffusion,用Ebsynth utility在视频选帧图重绘,第一步报错,蒙版和帧图没法生成,怎么处理啊
- ¥15 请把下列每一行代码完整地读懂并注释出来
- ¥15 pycharm运行main文件,显示没有conda环境
- ¥15 易优eyoucms关于二级栏目调用的问题
- ¥15 寻找公式识别开发,自动识别整页文档、图像公式的软件
- ¥15 为什么eclipse不能再下载了?
- ¥15 编辑cmake lists 明明写了project项目名,但是还是报错怎么回事
- ¥15 关于#计算机视觉#的问题:求一份高质量桥梁多病害数据集
- ¥15 特定网页无法访问,已排除网页问题