难以理解平衡分区的逻辑

Question

我正在解决 this link 的平衡分区问题。在这个问题中，我们必须将数组分成相等的部分，使得它们的总和之间的差异最小。所以，我找到的解决方案是考虑所有情况，一个元素是否将包含在一组中意味着我们必须尝试所有 2^n 种情况。

我提出了一个使用位操作划分数组的解决方案，但我不明白其中的逻辑。我在下面发布代码。有大佬告诉我他是怎么划分数组的吗？

#include<bits/stdc++.h>
using namespace std;
#define N 11

void solve(int a[N])
{
    long long x,y,v1,v2,res,i,j;
    long long val=1<<N;
    res=INT_MAX;
    for(i=0;i<val;i++)
    {
        x=y=v1=v2=0;
        for(j=0;j<N;j++)
        {
            if(i & (1<<j))
            {
                x++;
                v1+=a[j];
            }
            else
            {
                y++;
                v2+=a[j];
            }
        }
        if(abs(x-y)<=1) res=min(res,abs(v1-v2));
    }
    cout<<res<<endl;
}
int main()
{
    int a[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4};
    solve(a);
    return 0;
}

Answer 1

为了优化，您可以尝试对每个 cicle 子集的第一个和最后一个元素求和，因此避免对子集的所有元素进行 cicling，但 cicling 的次数仅等于子集的一半尺码..

在您的示例中，外部循环迭代保持不变，而内部循环减少了 2：

(for(j=0; j<(N/2); j++)

以及分组子集元素的总和：

v(1|2)+=(a[j] + a[N-j]);

难以理解平衡分区的逻辑

Having difficulty in understanding the logic of balanced partitioning

c++

arrays

algorithm

bit-manipulation

np-complete