分区问题 分区问题英語Partition problem是数论和计算机科学领域的问题目的是把一个多重集 S displaystyle S 分为 S  displaystyle S 和 S  displaystyle S 两个子集要求 S  displaystyle S 和 S  displaystyle S 这两个集合中所有数的和相等尽管分区问题属于NP完全问题但是依然存在伪多项式时间的动态规划解法而且在很多情况下也存在启发式的解法能够求出最优解或近似最优解正是基于这一点这类问题也被称为最简单的难题 分区问题存在一个最佳化問題该问题是将 S displaystyle S 分为 S  displaystyle S 和 S  displaystyle S 要求 S  displaystyle S 中元素的和与 S  displaystyle S 中元素的和相差最小这一问题属于NP困难问题但在实践中依旧存在高效的解法 分区问题是以下两个相关问题的特殊情况 子集和问题从集合 S displaystyle S 找到一个子集使其所有元素的和等于一给定值 T displaystyle T 分区问题就是T为 S displaystyle S 所有元素之和的   displaystyle frac  时的特殊情况 多路数字分区将集合 S displaystyle S 分为 k displaystyle k 个子集要求每个子集的元素之和都相等分区问题就是 k   displaystyle k 时的特殊情况 但是需要注意的是三分区问题与分区问题有很大不同三分区问题要求每个子集中都有个元素三分区问题比分区问题更难甚至连伪多项式时间算法都不存在除非满足PNP