Pythonで解く「最小の十分なチーム」問題：ビットマスクと動的計画法による最適解

問題の概要

あるプロジェクトにおいて、必要なスキルのリスト req_skills と、人物のリストが与えられているとします。i番目の人物 people[i] には、その人が持っているスキルのリストが格納されています。

ここで「十分なチーム（sufficient team）」とは、req_skills 内のすべての必須スキルについて、そのスキルを持つメンバーが少なくとも1人含まれているような人物の集合として定義されます。チームは各人物のインデックスで表現でき、たとえばチームが [0, 1, 3] の場合、これは people[0]、people[1]、people[3] の3人が選ばれたことを意味します。

この問題では、可能な限り小さいサイズのチームを見つける必要があります。答えは任意の順序で返して構いません。また、必ず答えが存在することが保証されています。

たとえば、入力が req_skills = ["java", "flutter", "android"]、people = [["java"], ["android"], ["flutter", "android"]] の場合、出力は [0, 2] になります。

解法のアプローチ

この問題は、各スキルの組み合わせをビットフラグ（2進数）で表現し、動的計画法（DP）と組み合わせることで効率的に解けます。以下の手順で進めます。

• dp: 辞書（マップ）を用意し、キー 0 に空のリストを対応させて初期化します。
• key: 各スキル名をインデックス番号に対応付ける辞書を作成します。
• people 配列からインデックス i と人物 p のペアを順に取り出し、以下を処理します。
  • current_skill を 0 で初期化します。
  • p に含まれる各スキル skill について、current_skill に 2^key[skill] をOR演算で加算していきます。
  • dp 内のすべての (skill_set, members) のペアに対して以下を確認します。
    • total_skill を skill_set OR current_skill として計算します。
    • total_skill が skill_set と同じ場合、この人物を追加しても状態が変わらないため、次の反復へスキップします。
    • total_skill が dp に存在しない、または既存の dp[total_skill] のサイズが members + 1 より大きい場合は、dp[total_skill] = members + [i] で更新します。
• 最後に dp[(1 << len(req_skills)) - 1] を返します。これはすべての必須スキルを網羅した状態に対応するキーです。

実装例

class Solution(object):
   def smallestSufficientTeam(self, req_skills, people):
      dp = {0:[]}
      key = {v:i for i,v in enumerate(req_skills)}
      for i,p in enumerate(people):
         current_skill = 0
         for skill in p:
         current_skill |= 1<< key[skill]
      for skill_set, members in dp.items():
         total_skill = skill_set|current_skill
         if total_skill == skill_set:
            continue
         if total_skill not in dp or len(dp[total_skill])>
len(members)+1:
            dp[total_skill] = members + [i]
      return dp[(1<<len(req_skills)) - 1]
ob = Solution()
print(ob.smallestSufficientTeam(["java","flutter","android"],
[["java"],["android"],["flutter","android"]]))

入力

["java","flutter","android"]
[["java"],["android"],["flutter","android"]]

出力

[0,2]

まとめ

この手法では、スキルの集合を整数のビット列として管理することで、状態数を最大でも 2^n 通り（n は必須スキルの数）に抑えたDPテーブルを構築できます。全人物の組み合わせを総当たりする方法と比べて計算量を大幅に削減でき、実務的な規模の入力でも高速に最小チームを求められるのが大きな利点です。