c++ - 有人可以解释这个平衡分区的源代码吗？

Question

有人可以详细解释这段代码吗？我试过调试它，但我不知道它是如何产生结果的。我一直在寻找问题的解决方案，这是我偶然发现的代码，它产生了准确的解决方案，我想知道它是如何工作的。非常感谢。

#include <iostream>
#include <stdio.h>   
#include <math.h>
#include <stdlib.h>
#include <limits.h>
using namespace std;


int BalancedPartition ( int a[] , int n ){

int sum = 0;
for( int i = 0 ; i < n ; i++)
    sum += a[i];

int *s = new int[sum+1];

s[0] = 1;
for(int i = 1 ; i < sum+1 ; i++)    s[i] = 0;

int diff = INT_MAX , ans;

for(int i = 0 ; i < n ; i++)
{
    for(int j = sum ; j >= a[i] ; j--)
    {
        s[j] = s[j] | s[j-a[i]];
        if( s[j] == 1 )
        {
            if( diff > abs( sum/2 - j) )
            {
                diff = abs( sum/2 - j );
                ans = j;
            }

        }
    }
}
return sum-ans-ans;
}

int main()
{
    int n,result, arr[300];
    cin >>n;
    for(int i = 0; i < n; i++)
    {
        cin>>arr[i];
}
result = BalancedPartition(arr,n);
cout <<abs(result); // The difference between the sums of the two subsets

return 0;
}

Answer 1

函数BalancedPartition 首先计算数组a 元素的总和，并将其存储在sum 中。然后它分配一个数组 s，该数组由可能的子集求和值索引。它用作跟踪内部 for 循环进度的簿记结构。如果s[j]为1，则表示值j已经被处理，其中值j表示元素的某个子集的总和在数组 a 中。最初，只有 s[0] 被设置为 1，这对应于没有元素的总和(空子集)。 diff用于计算求和最接近sum值二分之一的子集，这个子集求和值存储在ans中。一旦 ans 被正确计算，返回的值是 ans 中未使用的元素的总和与 ans 本身的差值，即， (sum - ans) - ans。所以，剩下的就是双 for 循环，看看它如何正确地到达 diff 和 ans。

外层 for 循环通过数组 a 的所有索引迭代 i。内部循环通过所有可能的子集求和值迭代 j，从 sum 开始。但是，如果该值可从先前识别的子集总和导出，则它仅识别子集总和值。也就是说，对于 j 的任何给定迭代，仅当 s[j - a[i]] 为 1 时，s[j] 才变为 1 . 由于最初仅识别空子集，因此第一次迭代仅识别s[a[0]]。第二次迭代识别 s[a[1]] 和 s[a[0]+a[1]]。第三次迭代识别s[a[2]]、s[a[0]+a[2]]、s[a[1]+a [2]] 和 s[a[0]+a[1]+a[2]]。如果您识别出该模式，则可以为算法的正确性制定归纳论证。