在列表中查找包含特定值的最小元素数

Question

一位招聘人员想组建一个具有不同技能的团队，他想挑选能够涵盖所有所需技能的最少人数。

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

代码应输出招聘人员可以找到的最小团队规模（最少人数）和指示要招聘到团队的人员的具体 ID 的值。

我用暴力实现代码如下，但由于一些数据超过数千，看来我需要用 heuristic 方法来解决。在这种情况下，可能会有大概的答案。

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

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

Answer 1

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

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)

在列表中查找包含特定值的最小元素数

Find minimum number of elements in a list that covers specific values

python

combinations

heuristics

brute-force

approximation