当前位置：首页 > article >正文

LC-1125. 最小的必要团队（状态压缩 + 0-1背包）

article 2024/11/18 20:31:18

1125. 最小的必要团队

难度困难107

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

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

例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。

请你返回任一规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。

示例 1：

输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
输出：[0,2]

示例 2：

输入：req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
输出：[1,2]

提示：

1 <= req_skills.length <= 16
1 <= req_skills[i].length <= 16
req_skills[i] 由小写英文字母组成
req_skills 中的所有字符串 互不相同
1 <= people.length <= 60
0 <= people[i].length <= 16
1 <= people[i][j].length <= 16
people[i][j] 由小写英文字母组成
people[i] 中的所有字符串 互不相同
people[i] 中的每个技能是 req_skills 中的技能
题目数据保证「必要团队」一定存在

状态压缩 + 0-1背包

题解：https://leetcode.cn/problems/smallest-sufficient-team/solution/zhuang-ya-0-1-bei-bao-cha-biao-fa-vs-shu-qode/

记忆化搜索

class Solution {
    // 把people堪称物品（集合），reqskills看成背包容量（目标集合），本题就是集合版的0-1背包问题
    // 状态压缩：为了方便计算，把reqskill的每个字符串映射到下标上，然后把每个people[i]映射转换成数字集合，再压缩成二进制数
    // 本题用到的位运算技巧：
    //     1.将元素x变为集合{x} : 1 << x
    //     2.判断元素x是否在集合A中 ： ((A >> x) & 1) == 1
    //     3.计算两个集合 A,B 的并集 A : A | B
    //     4.A\B在集合A中去掉集合B的元素 : A & ~B
    //     5.全集U : (1 << n) - 1
    private long all;
    private int[] mask;
    private long[][] memo;
    public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {
        var sid = new HashMap<String, Integer>();
        int m = reqSkills.length;
        for (int i = 0; i < m; ++i)
            sid.put(reqSkills[i], i); // 字符串映射到下标

        int n = people.size();
        mask = new int[n];
        for (int i = 0; i < n; ++i)
            for (var s : people.get(i)) // 把 people[i] 压缩成一个二进制数 mask[i]
                mask[i] |= 1 << sid.get(s);

        int u = 1 << m;
        memo = new long[n][u];
        for (int i = 0; i < n; i++)
            Arrays.fill(memo[i], -1); // -1 表示还没有计算过
        all = (1L << n) - 1;
        long res = dfs(n - 1, u - 1);

        var ans = new int[Long.bitCount(res)];
        for (int i = 0, j = 0; i < n; ++i)
            if (((res >> i) & 1) > 0)
                ans[j++] = i; // 所有在 res 中的下标
        return ans;
    }

    private long dfs(int i, int j){
        if(j == 0) return 0; // 背包已装满
        if(i < 0) return all; // // 没法装满背包，返回全集，这样下面比较集合大小会取更小的
        if (memo[i][j] != -1) return memo[i][j];
        long res = dfs(i - 1, j); // 不选 mask[i]
        long res2 = dfs(i - 1, j & ~mask[i]) | (1L << i); // 选 mask[i]
        return memo[i][j] = Long.bitCount(res) < Long.bitCount(res2) ? res : res2;
    }
}

递推：

class Solution {
    public int[] smallestSufficientTeam(String[] reqSkills, List<List<String>> people) {
        var sid = new HashMap<String, Integer>();
        int m = reqSkills.length;
        for (int i = 0; i < m; ++i)
            sid.put(reqSkills[i], i); // 字符串映射到下标

        int n = people.size(), u = 1 << m;
        // f[i+1][j] 表示从前 i 个集合中选择一些集合，并集等于 j，需要选择的最小集合
        var f = new long[n + 1][u];
        Arrays.fill(f[0], (1L << n) - 1); // 对应记忆化搜索中的 if (i < 0) return all;
        f[0][0] = 0;
        for (int i = 0; i < n; ++i) {
            int mask = 0;
            for (var s : people.get(i)) // 把 people[i] 压缩成一个二进制数 mask
                mask |= 1 << sid.get(s);
            for (int j = 1; j < u; ++j) {
                long res = f[i][j]; // 不选 mask
                long res2 = f[i][j & ~mask] | (1L << i); // 选 mask
                f[i + 1][j] = Long.bitCount(res) < Long.bitCount(res2) ? res : res2;
            }
        }

        long res = f[n][u - 1];
        var ans = new int[Long.bitCount(res)];
        for (int i = 0, j = 0; i < n; ++i)
            if (((res >> i) & 1) > 0)
                ans[j++] = i; // 所有在 res 中的下标
        return ans;
    }
}