论文部分内容阅读
对给定规模为ｎ的集合Ｓ，其每一个规模至多为ｋ的子集对应一个权．本文研究如何将Ｓ分为 个互不相交的规模至多为ｋ的子集且满足权和最大的问题．我们证明了该问题当ｋ＝２时是多项式时间可解的；当ｋ≥３时为ＮＰ－完全的；同时给出了一个Ｏ（ｎ￣（ｋ＋１））时间的启发式算法，所得到的解与最优解之比不小于１／ｋ．