分区问题

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

分区问题存在一个最佳化问题，该问题是将${\displaystyle S}$分为${\displaystyle S_{1}}$和${\displaystyle S_{2}}$，要求${\displaystyle S_{1}}$中元素的和与${\displaystyle S_{2}}$中元素的和相差最小。这一问题属于NP困难问题，但在实践中依旧存在高效的解法。^[4]

分区问题是以下两个相关问题的特殊情况：

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