在涵盖特定值的列表中查找最小数量的元素

debugcn 发表于 Dev

阿拉斯

招聘人员希望组建一支具有不同技能的团队，他希望选择能够满足所有所需技能的最低人数。

N代表人数，K是需要包括的独特技能的数量。列表spec_skill = [[1,3],[0,1,2],[0,2,4]]提供有关每个人的技能的信息。例如，人0有技能1 and 3，人1有技能0, 1 and 2等等。

该代码应输出招聘人员可以找到的最小团队人数（最少人数）和指示要招聘到团队中的特定人员ID的值。

我使用如下代码实现了代码，但是由于某些数据超过数千，因此似乎需要使用启发式方法来解决。在这种情况下，可能会有近似答案。

任何建议如何用启发式方法解决它的建议将不胜感激。

N,K = 3,5
spec_skill = [[1,3],[0,1,2],[0,2,4]]

A = list(range(K))
set_a = set(A)

solved = False
for L in range(0, len(spec_skill)+1):
    for subset in itertools.combinations(spec_skill, L):
        s = set(item for sublist in subset for item in sublist)
        if set_a.issubset(s):
            print(str(len(subset)) + '\n' + ' '.join([str(spec_skill.index(item)) for item in subset]))
            solved = True
            break
    if solved: break

全脑

这是我的方法。代码中可能存在潜在的优化可能性，但基本思想应该是可以理解的。

import random
import time
def man_power(lst, K, iterations=None, period=0):
    """
    Specify a fixed number of iterations
    or a period in seconds to limit the total computation time.
    """

    # mapping each sublist into a (sublist, original_index) tuple
    lst2 = [(lst[i], i) for i in range(len(lst))]
    mini_sample = [0]*(len(lst)+1)
    if period<0 or (period == 0 and iterations is None):
        raise AttributeError("You must specify iterations or a positive period")
    
            
    def shuffle_and_pick(lst, iterations):
        mini = [0]*len(lst)
        for _ in range(iterations):
            random.shuffle(lst2)
            skillset = set()
            chosen_ones = []
            idx = 0
            fullset = True
            # Breaks from the loop when all skillsets are found
            while len(skillset) < K:
                # No need to go further, we didn't find a better combination
                if len(chosen_ones) >= len(mini):
                    fullset = False
                    break
                before = len(skillset)
                skillset.update(lst2[idx][0])
                after = len(skillset)
                if after > before:
                    # We append with the orginal index of the sublist
                    chosen_ones.append(lst2[idx][1])
                idx += 1
            if fullset:
                mini = chosen_ones.copy()
        return mini
    
    # Estimates how many iterations we can do in the specified period
    if iterations is None:
        t0 = time.perf_counter()
        mini_sample = shuffle_and_pick(lst, 1)
        iterations = int(period / (time.perf_counter() - t0)) - 1
    
    mini_result = shuffle_and_pick(lst, iterations)
    if len(mini_sample)<len(mini_result):
        return mini_sample, len(mini_sample)
    else:
        return mini_result, len(mini_result)

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。