分区问题

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