algorithm - 最大非重叠子集？

Question

给定 100 个不同项目的 100 个（可能相交）子集，可以选择的最大子集数是多少，使得它们不重叠。

一种方法是：

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

这是Set packing，一个经典的 NP 完全问题。没有多项式时间解。