algorithm - 运行总和最大项最小化

Question

我正在制作一个物理优化器，其中关键部分由以下 CS 问题解决。

给定一个随机有符号整数数组。他们的总和为零。可以创建一个循环来保持运行总和，如下所示:

int running_sum = 0;
int sum_peak = 0;

for( int i = 0; i < size_of_array; i++ )
{
  running_sum += int_array[i];
  sum_peak = max( sum_peak, abs( running_sum ) );
}

assert( running_sum == 0 );

任务是通过置换初始 int_array 来最小化结果 sum_peak。到目前为止我的想法:天真的方法需要花费指数级的时间来运行。我所知道的任何 NP-C 问题似乎都没有表达这个问题。我想不出有什么方法可以将这个问题表示为图问题。

如果X是数组中最大的数(绝对值)，则max_sum的上下界分别为N和N/2。

编辑:示例。

{-4, -6, 10}:将列表重新排序为:{-6, 10, -4}，使sum_peak为-6。

{1, 1, 1, 1, -4}:将列表重新排序为:{ 1, 1, -4, 1, 1 }，使sum_peak为+2。

Answer 1

这可能是假的(如果我误解了问题的话)但有时最简单的方法就是最好的方法

• 如果 int 是无符号的，那么就没有帮助
• 如果有签名则:

1.输入数组

• 1,5,-2,7,-6,4,-10,-3,...

2.将有符号和无符号值分开并按值排序

• +1,+4,+5,+7,...
• -2,-3,-6,-10,...

3.重新排序原始数组

• 这可以通过更多方式完成
• 最简单的就是偶数是+，奇数是-
• +1,-2,+4,-3,+5,-6,+7,-10
• 速度很快但不是最优的
• 仍然会显着降低峰值

• 另一种选择是:

  1.while (sum>=0) 从+数组中添加数

  2.while (sum< 0) 从 -array 添加数

  3.当一个数组用完了，把没用的复制过来

• 不认为你可以做得比这更好

NP 完全从哪里来？？？

• 或者我遗漏了什么？？？

[编辑 1]

• 也可以对其进行改进以获得最佳解决方案，例如
• 使用较大的未使用值中的较小值来获得相反数组中最大未使用值的一半大小的总和...
• 也都可以就地完成

[编辑 2] 一些代码和测试

//---------------------------------------------------------------------------
void min_sum_peak()
    {
    const int N=1000;
    int in[N],out[N];
    int i,s,sp,e,ip0,im0,ip1,im1;
    // generate sum=0 random array to in and clear out (for easyier debug)
    for (s=0,i=1;i<N;i++)
        {
        in[i]=Random(1000)-500;
        s+=in[i];
        out[i]=0;
        } in[0]=-s; out[0]=0;

    // bubble sort in[]
    for (e=1;e;)
    for (e=0,i=1;i<N;i++)
     if (in[i-1]>in[i])
      { e=in[i-1]; in[i-1]=in[i]; in[i]=e; e=1; }


    // fill out[]
    #define peak { e=s; if (e<0) e=-e; if (sp<e) sp=e; }
    for (int mode=0;mode<3;mode++)
        {
        // scann for +/- boundary
        im0=-1; ip0=N;
        im1= 0; ip1=N-1;
        for (i=0;i<N;i++)
         if (in[i]<0) im0=i;
          else { ip0=i; break; }

        if (mode==0)            // even odd from smaller values (sp = ~2*max)
         for (i=0,s=0,sp=0;i<N;)
            {
            if (im0>=im1){ out[i]=in[im0]; s+=out[i]; im0--; i++; peak; }
            if (ip0<=ip1){ out[i]=in[ip0]; s+=out[i]; ip0++; i++; peak; }
            }
        if (mode==1)            // even odd from bigger values (sp = ~max)
         for (i=0,s=0,sp=0;i<N;)
            {
            if (im0>=im1){ out[i]=in[im1]; s+=out[i]; im1++; i++; peak; }
            if (ip0<=ip1){ out[i]=in[ip1]; s+=out[i]; ip1--; i++; peak; }
            }
        if (mode==2)            // -half sum to next max value (sp = ~0.5*max for big enough array)
            {
            for (i=0,s=0,sp=0;;)
                {
                if (im0<im1) break; // stop if any + or - valueas are exhausted
                if (ip0>ip1) break;
                if (s>=0)
                    {
                    if (+s+s<-in[im1]){ out[i]=in[ip0]; s+=out[i]; ip0++; i++; }
                    else              { out[i]=in[im1]; s+=out[i]; im1++; i++; }
                    }
                else{
                    if (-s-s<+in[ip1]){ out[i]=in[im0]; s+=out[i]; im0--; i++; }
                    else              { out[i]=in[ip1]; s+=out[i]; ip1--; i++; }
                    }
                peak;
                }
            for (;im0>=im1;){ out[i]=in[im0]; s+=out[i]; im0--; i++; peak; }
            for (;ip0<=ip1;){ out[i]=in[ip0]; s+=out[i]; ip0++; i++; peak; }
            }
        i=-in[0]; if (i<in[N-1]) i=in[N-1];
        // breakpoint here for approach assesment
        mode=mode;  // used approach
        i = i;      // abs max value
        s = s;      // sum
        sp=sp;      // sum peak
        }
    #undef peak { e=s; if (e<0) e=-e; if (sp<e) sp=e; }
    }
//---------------------------------------------------------------------------

• 模式 0 - 较小值的偶数 sp = ~2*max_abs_value
• 模式 1 - 较大值的偶数 sp = ~max_abs_value
• 模式 2 - 下一个最大值的一半总和 sp = ~0.5*max_abs_value
• 对于具有“均匀”分布的 +/- 值的足够大的阵列，模式 2 是预期的最佳
• 但如果数组很小(例如 N=20)，则模式 1 获胜
• 模式 0 一点也不好