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