3

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

#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;
}
4

1 回答 1

1

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

外部for循环遍历i数组的所有索引a。内部循环遍历j所有可能的子集总和值，从sum. 但是，如果该值可从先前识别的子集总和中导出，则它仅识别子集总和值。也就是说，对于 的任何给定迭代j，仅当 为s[j]1 时才变为s[j - a[i]]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]]

于 2013-02-28T18:42:51.107 回答