跳转至

最小的必要团队

实际上就是集合覆盖问题，最优集合覆盖是经典NP-困难问题。

作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。

所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：

例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。 请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。

动态规划

我们可以用一个二进制整数来代表每个候选人。用或运算来代表同时选取两个候选人。

技能清单的长度为n，那么每个人都是一串长度为n的二进制整数。

people_skill = []
for p in people:
    num = 0
    for i, s in enumerate(req_skills):
        if s in p:
            num += 1 << i # 这是2 ** i 的位运算写法
    people_skill.append(num)

我们最终就是选取最少的候选人，使得他们的数字经过或运算之后是全是1。

为了实现这个目标，我们考虑动态规划。假设dp[x]是为了凑出技能组合x，需要的最佳团队。

显然可以初始化为：

n = len(req_skills) # 共计n个技能
dp = [None] * (1 << n)  # 初始化为None
dp[0] = []  # 对于0，不需要人
for i, p in enumerate(people_skill):
    dp[p] = [i]  # 对于p，只需要i这一人

此后，我们每次都去新的技能组合：

# 遍历dp列表（已有的最佳团队）
for prev, comb in enumerate(dp):
    # 只看那些已经有值的位置
    if comb is None:
        continue
    # 考虑加入一个新的i人
    for i, p in enumerate(people_skill):
        # 对于new这个技能组合
        new = prev | p
        # 如果没有访问过这个组合，或者当前组合加上i人比已有的组合更短
        if dp[new] is None or len(comb) + 1 < len(dp[new]):
            dp[new] = dp[prev] + [i]

全部更新完毕后，dp[-1]就是最终答案了。

当然，两层循环也可以互换位置，不影响最终结果：

# 考虑加入一个新的i人
for i, p in enumerate(people_skill):
    # 遍历dp列表（已有的最佳团队）
    for prev, comb in enumerate(dp):
        # 只看那些已经有值的位置
        if comb is None:
            continue
        # 对于new这个技能组合
        new = prev | p
        # 如果没有人达到过这个组合，或者当前组合加上p比已有的组合更短
        if dp[new] is None or len(dp[prev]) + 1 < len(dp[new]):
            dp[new] = dp[prev] + [i]
dp[-1]

BFS

前面的处理保持不变，依然是把每个人表示为一个二进制整数。

不过这次我们使用BFS搜索。依次考虑1人团队、2人团队、3人团队。直到组合出我们需要的团队就停止搜索，进行回溯。

def min_or_cover_with_indices(nums, n):
    # 我们的目标是全覆盖
    target = (1 << n) - 1
    if target == 0:
        return 0, []  # 当n为0时，不需要任何数字

    # 使用字典记录前驱状态和选择的数字索引
    predecessor = {0: (None, None)}
    queue = [0]

    # 使用BFS搜索，每次新添一个人进去
    while queue:
        print(predecessor)
        current_mask = queue.pop(0)
        # 遍历所有数字
        for idx, num in enumerate(nums):
            new_mask = current_mask | num
            if new_mask not in predecessor:
                predecessor[new_mask] = (current_mask, idx)
                queue.append(new_mask)
            # 达到目标就回溯路径，收集所选索引
            if new_mask == target:
                path = []
                mask = new_mask
                while predecessor[mask][0] is not None:
                    prev_mask, num_idx = predecessor[mask]
                    path.append(num_idx)
                    mask = prev_mask
                return len(path), path # 题目保证了一定有解，所以一定会在这里返回
    return None # 当然我们也可以加一个无解的返回值

暴力搜索

当然，我们可以直接进行组合暴力搜索。

from itertools import combinations
from functools import reduce
def brute_force():
    for num in range(1, len(people_skill) + 1):
        for comb in combinations(people_skill, num):
            if reduce(lambda x,y: x|y, comb) == (1 << len(req_skills)) - 1:
                return [people_skill.index(i) for i in comb]

不过很难通过比较大的例子。

最后更新: 2025-05-29 02:42:18
创建日期: 2025-04-17 21:54:37

评论