分區問題

分區問題（英語：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]

實例

現有多重集${\displaystyle S={3,1,1,2,2,1}}$，可以被分為${\displaystyle S_{1}={1,1,1,2}}$以及${\displaystyle S_{2}={2,3}}$，兩者元素之和皆為5。