最小的必要团队【LC1125】
作为项目经理，你规划了一份需求的技能清单
req_skills，并打算从备选人员名单people中选出些人组成一个「必要团队」（ 编号为i的备选人员people[i]含有一份该备选人员掌握的技能列表）。所谓「必要团队」，就是在这个团队中，对于所需求的技能列表
req_skills中列出的每项技能，团队中至少有一名成员已经掌握。可以用每个人的编号来表示团队中的成员：
- 例如，团队
team = [0, 1, 3]表示掌握技能分别为people[0]，people[1]，和people[3]的备选人员。
请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按 任意顺序 返回答案，题目数据保证答案存在。
知道是01背包 状态压缩 但是代码写不出来
最近的每日一题还都挺复杂
- 思路每位备选人员有选或者不选两种可能，而我们最终的目标是使找到具有所有技能的最少员工，该问题实质上为01背包问题。
- 物品为每个员工的技能，背包容量为所有需要的技能。【用状态压缩表示技能】
4.确定遍历顺序
一维dp
先遍历物品，再从后往前遍历背包重量
5。举例推导dp数组
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; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/smallest-sufficient-team/solutions/2214387/zhuang-ya-0-1-bei-bao-cha-biao-fa-vs-shu-qode/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
