Jon*_*n W 11 algorithm knapsack-problem satisfiability
只是一个好奇的问题.还记得在课堂小组中,教授会把人分成一定数量的小组(n)吗？
n
我的一些教授会列出n一个想要与之合作的n人和一个不想与每个学生一起工作的人的名单,然后神奇地将n学生与他们喜欢的人匹配的小组变成一组,避免与他们一起工作他们不喜欢的人.
对我来说,这个算法听起来很像背包问题,但我想我会问你对这类问题的解决方法是什么.
编辑:找到一篇描述与我的问题完全相同的ACM文章.为了似曾相识,请阅读第二段.
Seb*_*olm 5
对我而言,这听起来更像某种集团问题.
我看到问题的方式,我将设置以下图表:
然后将图形划分为大小为n的集团.(假设学生人数可以被n整除)
如果这是不可能的,我可能会让边缘上的第一个约束滑动,并且在两个人之间有边缘,只要它们都没有明确表示他们不想与另一个人合作.
至于有效解决这个问题的方法,我不知道,但这有望让你更接近对这个问题的一些见解.
归档时间：
15 年，7 月 前
查看次数：
2946 次
最近记录：
11 年，2 月 前