查看“︁Set packing”︁的源代码

{{unreferenced|time=2014-06-16T14:54:34+00:00}}
{{noteTA
|G1=IT
}}

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

== 题目描述 ==

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

形式化的定义：给定全集<math>\mathcal{U}</math>，和<math>\mathcal{U}</math>的一组子集<math>\mathcal{S}</math>。''packing''指一个集合<math>\mathcal{C}</math>满足<math>\mathcal{C}\subseteq\mathcal{S}</math>且<math>\mathcal{C}</math>中任意两个集合互不相交。定义<math>|\mathcal{C}|</math>为''packing''的大小。

对于 set packing 的[[決定性問題]]，输入是 <math>(\mathcal{U},\mathcal{S})</math> 对和一个整数 <math>k</math>，求是否存在一个大小至少为<math>k</math>的 packing 。对于 set packing 的[[最优性問題]]，输入是 <math>(\mathcal{U},\mathcal{S})</math> 对，求最大的 packing 。

[[Category:计算机逻辑]]
[[Category:形式方法]]
[[Category:NP完全问题]]