Set packing

Set packing 问题是复杂性理论和组合数学中一个经典的NP完全问题，是卡普的二十一个NP-完全问题之一。

给定一个有限集合 和一些 的子集，求问是否可以其中的 个子集，他们两两不相交。

形式化的定义：给定全集${\displaystyle \mathcal{U}}$指一个集合${\displaystyle \mathcal{C}}$的大小。

对于 set packing 的决定性问题，输入是 ${\displaystyle (\mathcal{U},\mathcal{S})}$ 对和一个整数 ${\displaystyle k}$，求是否存在一个大小至少为${\displaystyle k}$的 packing 。对于 set packing 的最优性问题，输入是 ${\displaystyle (\mathcal{U},\mathcal{S})}$ 对，求最大的 packing 。