我一直在寻找这个问题的名称,我必须做一个作业,确定它是P还是NP,等等,但我在任何地方都找不到。问题是:
你有一个有K个房间的学生宿舍,以及一个申请一个房间的N名学生的名单(一个房间只容纳一个学生)。每个候选人都有一份他不能同在同一所房子里的学生名单。
实现这样一种算法:给定K(房间数)、申请房间的学生列表和学生之间不兼容的列表,然后找出由于在房间中的学生的不兼容列表而不能在房间里的学生列表。
对不起,如果已经有人问起了,我哪儿也找不到!
https://stackoverflow.com/questions/26864803
复制相似问题