有许多论文描述了集合划分的各种高级算法。这里仅列出其中两个：
-
“一个完整的随时数字划分算法” http://www.sciencedirect.com/science/article/pii/S0004370298000861作者：理查德·E·科尔夫。
-
“子集和问题的高效全多项式近似方案” http://www.sciencedirect.com/science/article/pii/S0022000003000060汉斯·凯勒等人。
老实说，我不知道他们中的哪一个提供了更有效的解决方案。解决 SPOJ 问题可能不需要这些高级算法。科尔夫的论文还是很有用的。那里描述的算法非常简单（易于理解和实现）。他还概述了几种更简单的算法（在第 2 节中）。因此，如果您想了解 Horowitz-Sahni 或 Schroeppel-Shamir 方法（下面提到）的详细信息，您可以在 Korf 的论文中找到它们。此外（在第 8 节中）他写道，随机方法并不能保证足够好的解决方案。因此，通过爬山、模拟退火或禁忌搜索等方法不太可能获得显着的改进。
I tried several simple algorithms and their combinations to solve partitioning problems with size up to 10000, maximum value up to 1014, and time limit 4 sec. They were tested on random uniformly distributed numbers. And optimal solution was found for every problem instance I tried. For some problem instances optimality is guaranteed by algorithm, for others optimality is not 100% guaranteed, but probability of getting sub-optimal solution is very small.
对于尺寸最大为 4（左侧绿色区域）的 Karmarkar-Karp 算法始终给出最佳结果。
对于最大 54 的大小，暴力算法足够快（红色区域）。可以选择 Horowitz-Sahni 或 Schroeppel-Shamir 算法。我使用 Horowitz-Sahni 是因为它对于给定的限制似乎更有效。 Schroeppel-Shamir 使用的内存要少得多（所有内容都适合 L2 缓存），因此当其他 CPU 核心执行一些内存密集型任务或使用多个线程进行集合分区时，它可能更可取。或者在没有严格时间限制的情况下解决更大的问题（Horowitz-Sahni 只是耗尽内存）。
When size multiplied by sum of all values is less than 5*109 (blue area), dynamic programming approach is applicable. Border between brute force and dynamic programming areas on diagram shows where each algorithm performs better.
右侧的绿色区域是 Karmarkar-Karp 算法以几乎 100% 的概率给出最佳结果的地方。这里有如此多的完美分区选项（增量为 0 或 1），Karmarkar-Karp 算法几乎肯定会找到其中之一。可以发明 Karmarkar-Karp 总是给出次优结果的数据集。例如{17 13 10 10 10 ...}。如果将其乘以某个大数，KK 和 DP 都无法找到最优解。幸运的是，这样的数据集在实践中不太可能出现。但出题者可以添加这样的数据集，使比赛变得更加困难。在这种情况下，您可以选择一些高级算法以获得更好的结果（但仅限于图表上的灰色和右绿色区域）。
我尝试了两种方法来实现 Karmarkar-Karp 算法的优先级队列：使用最大堆和使用排序数组。排序数组选项在线性搜索中似乎稍快，而在二分搜索中则明显更快。
黄色区域是您可以在有保证的最佳结果（使用 DP）或仅具有高概率的最佳结果（使用 Karmarkar-Karp）之间进行选择的地方。
最后，灰色区域，其中任何简单算法本身都无法给出最佳结果。在这里，我们可以使用 Karmarkar-Karp 来预处理数据，直到它适用于 Horowitz-Sahni 或动态规划。在这个地方也有很多完美的分区选项，但比绿色区域少，所以Karmarkar-Karp本身有时可能会错过适当的分区。更新：正如@mhum 所指出的，没有必要实现动态编程算法来使事情正常工作。 Horowitz-Sahni 与 Karmarkar-Karp 预处理就足够了。但 Horowitz-Sahni 算法必须在上述时间限制内处理最大 54 的大小，以（几乎）保证最佳分区。所以C++或其他具有良好优化编译器和快速计算机的语言是优选的。
以下是我如何将 Karmarkar-Karp 与其他算法结合起来：
template<bool Preprocess = false>
i64 kk(const vector<i64>& values, i64 sum, Log& log)
{
log.name("Karmarkar-Karp");
vector<i64> pq(values.size() * 2);
copy(begin(values), end(values), begin(pq) + values.size());
sort(begin(pq) + values.size(), end(pq));
auto first = end(pq);
auto last = begin(pq) + values.size();
while (first - last > 1)
{
if (Preprocess && first - last <= kHSLimit)
{
hs(last, first, sum, log);
return 0;
}
if (Preprocess && static_cast<double>(first - last) * sum <= kDPLimit)
{
dp(last, first, sum, log);
return 0;
}
const auto diff = *(first - 1) - *(first - 2);
sum -= *(first - 2) * 2;
first -= 2;
const auto place = lower_bound(last, first, diff);
--last;
copy(last + 1, place, last);
*(place - 1) = diff;
}
const auto result = (first - last)? *last: 0;
log(result);
return result;
}
完整 C++11 实现的链接。 http://ideone.com/0QYVDA该程序仅确定分区总和之间的差异，它不报告分区本身。Warning:如果您想在可用内存少于 1 Gb 的计算机上运行它，请减少kHSLimit持续的。
