最小的必要团队

题目

1125. 最小的必要团队

---

作为项目经理，你规划了一份需求的技能清单 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 中的技能
• 题目数据保证「必要团队」一定存在

题解

方法一：

思路

每个人有选与不选，我们需要选尽可能少的人来达到所有需要的技能。

将其转化为01背包问题。
可以将每个人的看作物品。背包总容量是所需的技能列表。
每个人的所掌握的技能看作物品的体积，每个人的价值是1，需要求让背包装满且价值最小的一种方案。

与以往01背包不同的是这里的背包容量不再是一个数，而是一个集合，而这个集合中元素不超过16，可以用二进制表示。

然后答案是需要构造一个最小人数的序列。人数不超过60，可以用longlong的二进制表示

另外如果人数超过64，我们可以修改一下状态的定义 f[i][j] 前i个人能否拥有j技能最小集合大小，
然后逆推f[m][(1<<n)-1]构造一个答案。

代码

class Solution {
public:
    using ll = long long;
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        unordered_map<string,int> mp;
        for (int i=0; i<req_skills.size(); i++) mp[req_skills[i]] = i;
        vector<int> peo;
        for (auto& i:people) {
            int x = 0;
            for (auto& j:i) x |= 1<<mp[j];
            peo.push_back(x);
        }
        auto cntbits = [](ll x) {
            if (x<0) return 64;
            int rt = 0;
            for (;x; x=x&(x-1LL)) rt++;
            return rt;
        };
        int n = req_skills.size();
        int m = people.size();
        ll f[m+1][1<<n]; // f[i][j] 前i个人拥有j技能集合的一个合法最小人数下标集合
        memset(f, -1, sizeof(f));
        f[0][0] = 0;
        for (int i=1; i<=m; i++) {
            for (int j=0; j<1<<n; j++) {
                if (cntbits(f[i-1][j&~peo[i-1]]|1LL<<i-1) > cntbits(f[i-1][j]))
                    f[i][j] = f[i-1][j];
                else 
                    f[i][j] = f[i-1][j&~peo[i-1]]|1LL<<i-1;
            }
        }
        ll u = f[m][(1<<n)-1];
        vector<int> rt;
        for (int i=0; i<m; i++) {
            if (u>>i&1) rt.push_back(i);
        }
        return rt;
    }
};

class Solution {
public:
    using ll = long long;
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        unordered_map<string,int> mp;
        for (int i=0; i<req_skills.size(); i++) mp[req_skills[i]] = i;
        vector<int> peo;
        for (auto& i:people) {
            int x = 0;
            for (auto& j:i) x |= 1<<mp[j];
            peo.push_back(x);
        }
        auto cntbits = [](ll x) {
            if (x<0) return 64;
            int rt = 0;
            for (;x; x=x&(x-1LL)) rt++;
            return rt;
        };
        int n = req_skills.size();
        int m = people.size();
        int f[m+1][1<<n]; // f[i][j] 前i个人能否拥有j技能最小集合大小
        memset(f, 0x3f, sizeof(f));
        f[0][0] = 0;
        for (int i=1; i<=m; i++) {
            for (int j=0; j<1<<n; j++) {
                f[i][j] = min(f[i-1][j], f[i-1][j&~peo[i-1]]+1);
                // cout << i << " " << j << " " << f[i][j] << endl;
            }
        }
        // 构造答案 逆推 f[m][(1<<n)-1] 由谁转移
        vector<int> rt;
        ll u = m, v = (1<<n)-1;
        while (u) {
            if (f[u][v] == f[u-1][v&~peo[u-1]]+1) v = v&~peo[u-1], rt.push_back(u-1);
            u--;
        }
        return rt;
    }
};