分区问题

分区问题（）是数论和计算机科学领域的问题，目的是把一个多重集S分为S_1和S_2两个子集，要求S_1和S_2这两个集合中所有数的和相等。尽管分区问题属于NP完全问题，但是依然存在伪多项式时间的动态规划解法，而且在很多情况下也存在启发式的解法，能够求出最优解或近似最优解。正是基于这一点，这类问题也被称为“最简单的难题”。

分区问题存在一个最佳化問題，该问题是将S分为S_1和S_2，要求S_1中元素的和与S_2中元素的和相差最小。这一问题属于NP困难问题，但在实践中依旧存在高效的解法。

分区问题是以下两个相关问题的特殊情况：
*子集和问题：从集合S找到一个子集，使其所有元素的和等于一给定值T（分区问题就是T为S所有元素之和的\frac{1}{2}时的特殊情况）
*多路数字分区：将集合S分为k个子集，要求每个子集的元素之和都相等（分区问题就是k=2时的特殊情况）
*但是需要注意的是，三分区问题与分区问题有很大不同，三分区问题要求每个子集中都有3个元素。三分区问题比分区问题更难，甚至连伪多项式时间算法都不存在，除非满足P=NP。