RPA百科-【算法题】最小分组问题

214人参与 |分类: 产品百科|时间: 2019年11月01日

问题

给定一个全集,代表所有可能的分组情况,全集中每个元素用正整数表示
输入:给定一个列表,列表中的每个元素都是一个个体,个体可以从全集中选择一种或多种分组情况,结果用元组表示
输出:一个字典,键为分组,值为这个分组下的所有个体,需要保证最后分得的组数量最少
另外,当可以从多个分组中任意选取时,优先考虑数值比较小的分组

>>> all = {1, 2, 3}
>>> func([(1, 2, 3), (2, 3), (1, 3)]){3: [(1, 2, 3), (2, 3), (1, 3)]}
>>> func([(1, 2, 3), (2, 3), (1,)]){1: [(1, 2, 3), (1,)], 2: [(2, 3)]}
>>> func([(1,), (1, 3), (2,), (2, 3)]){1: [(1,), (1, 3)], 2:[(2,), (2, 3)]}

以学生分班为例,用代码前三行说明:

  • all = {1, 2, 3}
    一共有 1 班 2 班 3 班三个班级

  • [(1, 2, 3), (2, 3), (1, 3)]
    有甲乙丙三个学生,甲可以选择任意一个班级,乙只能选择 2 班或 3 班,丙只能选择 1 班或 3 班

  • {3: [(1, 2, 3), (2, 3), (1, 3)]}
    这个结果的意思是只开一个 3 班,把三个学生都能放进来,这样需要开设的班级最少


来源:[jane小姐](微信/QQ号:1055692322),转载请保留出处和链接!

地址: