状态压缩dp
有什么好说的,先打它一波暴力
const h = [];
let hh = 0;
let min = Number.MAX_SAFE_INTEGER;
const isOk = function (ii, rl, people) {
const is = ii.toString(2);
const pl = people.length;
let n = 0;
for (let i = 0, il = is.length; i < il; i++) {
const ib = is[i];
if (ib === '1') {
++n;
people[pl - il + i].forEach(e => {
hh |= 1 << h[e];
});
}
}
if (hh === (1 << rl) - 1) {
if (n < min) {
min = n;
hh = 0;
return ii;
}
}
hh = 0
return false;
}
const smallestSufficientTeam = function (req_skills, people) {
const rl = req_skills.length, pl = people.length;
const max = 1 << pl;
let r, t;
for (let i = 0; i < rl; i++) {
h[req_skills[i]] = i;
}
for (let i = 1; i < max; i++) {
t = isOk(i, rl, people);
if (t) r = t;
}
const rr = [];
r = r.toString(2).split('')
for (let i = 0; i < r.length; i++) {
const e = r[i];
if (e === '1') {
rr.push(pl - r.length + i)
}
}
h = [];
hh = 0;
min = Number.MAX_SAFE_INTEGER;
return rr
};
当然是超时了, 好接下来用 c++ 写状压 dp 的代码
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<int> smallestSufficientTeam(vector<string> &req_skills, vector<vector<string>> &people)
{
map<int, vector<int>> res; // res[i] = {...v} 代表技能标志位为 i 的最少人数队列 v
unordered_map<string, int> skills;
int rl = req_skills.size();
int pl = people.size();
res[0] = {};
for (auto k = res.begin(); k != res.end(); k++)
{
cout << k->first << endl;
}
for (int i = 0; i < rl; i++)
{
skills[req_skills[i]] = i; // 把技能对应成一个个的二进制标志位
}
for (int i = 0; i < pl; i++)
{
int current_skill = 0;
for (int j = 0; j < people[i].size(); j++)
{
current_skill |= 1 << skills[people[i][j]];
}
for (auto k = res.begin(); k != res.end(); k++)
{
// cout << k->first << endl;
int combination = k->first | current_skill;
if (res.find(combination) == res.end() || res[combination].size() > 1 + res[k->first].size())
{
res[combination] = k->second;
res[combination].push_back(i);
}
}
}
return res[(1 << rl) - 1];
}
};