分割问题已知为NP难问题。根据问题的具体实例，我们可以尝试使用动态规划或一些启发式算法，例如差分（也称为Karmarkar-Karp算法）。
后者似乎非常适用于大数实例（这使得动态规划成为一个棘手的问题），但并不总是完美的。有没有一种高效的方法可以找到更好的解决方案（随机、禁忌搜索、其他近似算法）？
PS：这个问题背后有一些故事。自2004年7月以来，SPOJ上有一个挑战Johnny Goes Shopping。迄今为止，该挑战已被1087位用户解决，但只有11位用户比正确的Karmarkar-Karp算法实现得分更高（在当前评分下，Karmarkar-Karp算法给出11.796614点）。如何做得更好？（支持已接受提交的答案最想要，但请不要透露你的代码。）
有许多论文描述了各种高级算法来进行集合划分。以下仅列出其中两篇：
老实说，我不知道哪个算法提供的解决方案更有效。也许这些高级算法都不需要用来解决SPOJ问题。Korf的论文仍然非常有用。其中描述的算法非常简单（易于理解和实现）。此外，他还概述了几种更简单的算法（在第2节中）。因此，如果您想了解Horowitz-Sahni或Schroeppel-Shamir方法的详细信息（如下所述），可以在Korf的论文中找到它们。此外（在第8节中），他写道随机方法不能保证足够好的解决方案。因此，使用类似爬山，模拟退火或禁忌搜索等方法可能不会带来显着的改进。
我尝试了几种简单算法及其组合来解决大小为10000，最大值为1014，时间限制为4秒的分区问题。它们在随机均匀分布的数字上进行了测试。对于我尝试的每个问题实例，都找到了最优解。对于一些问题实例，算法可以保证最优性，而对于其他问题实例，最优性不能百分之百保证，但获得次优解的概率非常小。
对于大小不超过4的情况（左侧的绿色区域），Karmarkar-Karp算法始终给出最优结果。
对于大小不超过54的情况，暴力算法足够快（红色区域）。可以选择Horowitz-Sahni或Schroeppel-Shamir算法。我使用了Horowitz-Sahni算法，因为在给定的限制条件下，它似乎更有效。Schroeppel-Shamir使用的内存要少得多（一切都适合L2高速缓存），因此当其他CPU核心执行一些内存密集型任务或使用多个线程进行集合分区时，它可能更可取。或者解决时间限制不那么严格的更大问题（在这种情况下，Horowitz-Sahni会耗尽内存）。
当大小乘以所有值的总和小于5*109（蓝色区域）时，动态规划方法是适用的。图表上暴力算法和动态规划区域的边界显示每个算法的性能更好的位置。
右边的绿色区域是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++或其他具有良好优化编译器和快速计算机的语言更可取。
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实现链接。该程序仅确定分区和之间的差异，不会报告分区本身。 警告：如果您要在剩余内存少于1GB的计算机上运行它，请减少kHSLimit常量。
无论价值多少，一个简单、未经优化的Python实现“完整的Karmarkar Karp”(CKK)搜索过程[Korf88]——只稍微修改一下，在给定的时间限制（比如4.95秒）后退出搜索，并返回迄今为止找到的最佳解决方案——足以在SPOJ问题上获得14.204234的分数，超过了Karmarkar-Karp的分数。截至本文撰写之时，这是#3 on the rankings (见下面的编辑#2)
更易读的Korf CKK算法介绍可以在[Mert99]中找到。
编辑 #1 - 我已经尝试了两个对基本CKK算法的进一步改进：
"改进的有限差分搜索"（ILDS）[Korf96] 这是搜索树中路径的自然DFS排序的替代方法。它有倾向于在早期探索比常规深度优先搜索更多样化的解决方案。
"加速双向数字划分" [Cerq12] 这将CKK中一个修剪准则从叶节点内部的节点推广到叶节点上面5、6和7个级别的节点。
在我的测试用例中，这两种改进通常都比原始的CKK在减少探索的节点数（后者）和更早地获得更好的解决方案（前者）方面提供了明显的好处。然而，在SPOJ问题结构的限制下，这两种方法都不足以提高我的分数。
鉴于这个SPOJ问题的特殊性质（即：5秒时间限制和仅有一个特定且未公开的问题实例），很难给出关于如何实际提高分数的建议*。例如，我们应该继续追求替代搜索排序策略（例如：Wheeler Ruml列出的许多论文listed here）吗？或者我们应该尝试将一些形式的局部改进启发式算法纳入CKK找到的解决方案以帮助修剪？或者我们应该完全放弃基于CKK的方法，尝试动态规划方法？PTAS呢？如果不了解SPOJ问题中使用的具体实例的更多信息，很难猜测哪种方法会产生最大的收益。每种方法都有其优点和缺点，取决于给定实例的具体属性。* 除了简单地通过实现C++而不是Python来更快地运行相同的内容之外。
[Cerq12] Cerquides, Jesús 和 Pedro Meseguer. "Speeding Up 2-way Number Partitioning." ECAI. 2012, doi:10.3233/978-1-61499-098-7-223
[HS74] Horowitz, Ellis 和 Sartaj Sahni. "计算具有背包问题应用的分区。" Journal of the ACM (JACM) 21.2 (1974): 277-292.
[Korf88] Korf, Richard E. (1998), "一个完整的任何时候算法用于数字分区", 人工智能106 (2): 181–203, doi:10.1016/S0004-3702(98)00086-1,编辑：这是一种从Karmarkar-Karp差分开始，然后尝试优化所得到的分区的实现方法。
时间只允许的优化是将1从一个分区给另一个分区，以及在两个分区之间交换1与1。
我在开头实现的Karmarkar-Karp可能不准确，因为仅使用Karmarkar-Karp得到的得分为2.711483而不是OP引用的11.796614个点。当使用优化时，得分变为7.718049。
剧透警告：下面是C#提交代码
using System;
using System.Collections.Generic;
using System.Linq;
public class Test
{
// some comparer's to lazily avoid using a proper max-heap implementation
public class Index0 : IComparer<long[]>
{
public int Compare(long[] x, long[] y)
{
if(x[0] == y[0]) return 0;
return x[0] < y[0] ? -1 : 1;
}
public static Index0 Inst = new Index0();
}
public class Index1 : IComparer<long[]>
{
public int Compare(long[] x, long[] y)
{
if(x[1] == y[1]) return 0;
return x[1] < y[1] ? -1 : 1;
}
}
public static void Main()
{
// load the data
var start = DateTime.Now;
var list = new List<long[]>();
int size = int.Parse(Console.ReadLine());
for(int i=1; i<=size; i++) {
var tuple = new long[]{ long.Parse(Console.ReadLine()), i };
list.Add(tuple);
}
list.Sort((x, y) => { if(x[0] == y[0]) return 0; return x[0] < y[0] ? -1 : 1; });
// Karmarkar-Karp differences
List<long[]> diffs = new List<long[]>();
while(list.Count > 1) {
// get max
var b = list[list.Count - 1];
list.RemoveAt(list.Count - 1);
// get max
var a = list[list.Count - 1];
list.RemoveAt(list.Count - 1);
// (b - a)
var diff = b[0] - a[0];
var tuple = new long[]{ diff, -1 };
diffs.Add(new long[] { a[0], b[0], diff, a[1], b[1] });
// insert (b - a) back in
var fnd = list.BinarySearch(tuple, new Index0());
list.Insert(fnd < 0 ? ~fnd : fnd, tuple);
}
var approx = list[0];
list.Clear();
// setup paritions
var listA = new List<long[]>();
var listB = new List<long[]>();
long sumA = 0;
long sumB = 0;
// Karmarkar-Karp rebuild partitions from differences
bool toggle = false;
for(int i=diffs.Count-1; i>=0; i--) {
var inB = listB.BinarySearch(new long[]{diffs[i][2]}, Index0.Inst);
var inA = listA.BinarySearch(new long[]{diffs[i][2]}, Index0.Inst);
if(inB >= 0 && inA >= 0) {
toggle = !toggle;
}
if(toggle == false) {
if(inB >= 0) {
listB.RemoveAt(inB);
}else if(inA >= 0) {
listA.RemoveAt(inA);
}
var tb = new long[]{diffs[i][1], diffs[i][4]};
var ta = new long[]{diffs[i][0], diffs[i][3]};
var fb = listB.BinarySearch(tb, Index0.Inst);
var fa = listA.BinarySearch(ta, Index0.Inst);
listB.Insert(fb < 0 ? ~fb : fb, tb);
listA.Insert(fa < 0 ? ~fa : fa, ta);
} else {
if(inA >= 0) {
listA.RemoveAt(inA);
}else if(inB >= 0) {
listB.RemoveAt(inB);
}
var tb = new long[]{diffs[i][1], diffs[i][4]};
var ta = new long[]{diffs[i][0], diffs[i][3]};
var fb = listA.BinarySearch(tb, Index0.Inst);
var fa = listB.BinarySearch(ta, Index0.Inst);
listA.Insert(fb < 0 ? ~fb : fb, tb);
listB.Insert(fa < 0 ? ~fa : fa, ta);
}
}
listA.ForEach(a => sumA += a[0]);
listB.ForEach(b => sumB += b[0]);
// optimize our partitions with give/take 1 or swap 1 for 1
bool change = false;
while(DateTime.Now.Subtract(start).TotalSeconds < 4.8) {
change = false;
// give one from A to B
for(int i=0; i<listA.Count; i++) {
var a = listA[i];
if(Math.Abs(sumA - sumB) > Math.Abs((sumA - a[0]) - (sumB + a[0]))) {
var fb = listB.BinarySearch(a, Index0.Inst);
listB.Insert(fb < 0 ? ~fb : fb, a);
listA.RemoveAt(i);
i--;
sumA -= a[0];
sumB += a[0];
change = true;
} else {break;}
}
// give one from B to A
for(int i=0; i<listB.Count; i++) {
var b = listB[i];
if(Math.Abs(sumA - sumB) > Math.Abs((sumA + b[0]) - (sumB - b[0]))) {
var fa = listA.BinarySearch(b, Index0.Inst);
listA.Insert(fa < 0 ? ~fa : fa, b);
listB.RemoveAt(i);
i--;
sumA += b[0];
sumB -= b[0];
change = true;
} else {break;}
}
// swap 1 for 1
for(int i=0; i<listA.Count; i++) {
var a = listA[i];
for(int j=0; j<listB.Count; j++) {
var b = listB[j];
if(Math.Abs(sumA - sumB) > Math.Abs((sumA - a[0] + b[0]) - (sumB -b[0] + a[0]))) {
listA.RemoveAt(i);
listB.RemoveAt(j);
var fa = listA.BinarySearch(b, Index0.Inst);
var fb = listB.BinarySearch(a, Index0.Inst);
listA.Insert(fa < 0 ? ~fa : fa, b);
listB.Insert(fb < 0 ? ~fb : fb, a);
sumA = sumA - a[0] + b[0];
sumB = sumB - b[0] + a[0];
change = true;
break;
}
}
}
//
if(change == false) { break; }
}
/*
// further optimization with 2 for 1 swaps
while(DateTime.Now.Subtract(start).TotalSeconds < 4.8) {
change = false;
// trade 2 for 1
for(int i=0; i<listA.Count >> 1; i++) {
var a1 = listA[i];
var a2 = listA[listA.Count - 1 - i];
for(int j=0; j<listB.Count; j++) {
var b = listB[j];
if(Math.Abs(sumA - sumB) > Math.Abs((sumA - a1[0] - a2[0] + b[0]) - (sumB - b[0] + a1[0] + a2[0]))) {
listA.RemoveAt(listA.Count - 1 - i);
listA.RemoveAt(i);
listB.RemoveAt(j);
var fa = listA.BinarySearch(b, Index0.Inst);
var fb1 = listB.BinarySearch(a1, Index0.Inst);
var fb2 = listB.BinarySearch(a2, Index0.Inst);
listA.Insert(fa < 0 ? ~fa : fa, b);
listB.Insert(fb1 < 0 ? ~fb1 : fb1, a1);
listB.Insert(fb2 < 0 ? ~fb2 : fb2, a2);
sumA = sumA - a1[0] - a2[0] + b[0];
sumB = sumB - b[0] + a1[0] + a2[0];
change = true;
break;
}
}
}
//
if(DateTime.Now.Subtract(start).TotalSeconds > 4.8) { break; }
// trade 2 for 1
for(int i=0; i<listB.Count >> 1; i++) {
var b1 = listB[i];
var b2 = listB[listB.Count - 1 - i];
for(int j=0; j<listA.Count; j++) {
var a = listA[j];
if(Math.Abs(sumA - sumB) > Math.Abs((sumA - a[0] + b1[0] + b2[0]) - (sumB - b1[0] - b2[0] + a[0]))) {
listB.RemoveAt(listB.Count - 1 - i);
listB.RemoveAt(i);
listA.RemoveAt(j);
var fa1 = listA.BinarySearch(b1, Index0.Inst);
var fa2 = listA.BinarySearch(b2, Index0.Inst);
var fb = listB.BinarySearch(a, Index0.Inst);
listA.Insert(fa1 < 0 ? ~fa1 : fa1, b1);
listA.Insert(fa2 < 0 ? ~fa2 : fa2, b2);
listB.Insert(fb < 0 ? ~fb : fb, a);
sumA = sumA - a[0] + b1[0] + b2[0];
sumB = sumB - b1[0] - b2[0] + a[0];
change = true;
break;
}
}
}
//
if(change == false) { break; }
}
*/
// output the correct ordered values
listA.Sort(new Index1());
foreach(var t in listA) {
Console.WriteLine(t[1]);
}
// DEBUG/TESTING
//Console.WriteLine(approx[0]);
//foreach(var t in listA) Console.Write(": " + t[0] + "," + t[1]);
//Console.WriteLine();
//foreach(var t in listB) Console.Write(": " + t[0] + "," + t[1]);
}
}