algorithm - 最大非重複サブセット?

Question

100 個の異なる項目の 100 個の (交差する可能性がある) サブセットが与えられた場合、重複しないように選択できるサブセットの最大数はいくつですか。

これを行う1つの方法は次のとおりです。

for i in 100 downto 0
   foreach choice C of (100 choose i) subsets:
      if (no two elements of C overlap)
          return i;

しかし、明らかにこれは遅すぎます。多項式時間の解はありますか?

Answer 1

これは古典的な NP 完全問題である Setpacking です。多項式時間の解はありません。