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ます。一度ansansが正しく計算された場合、返される値は、 で使用されていない要素の合計とansそれ自体の差、つまり です(sum - ans) - ans。したがって、残っているのは二重forループで、どのように と に正しく到達するかを確認しdiffますans。

外側のforループiは、配列のすべてのインデックスを反復処理しますa。内側のループjは、 から始まるすべての可能なサブセット合計値を反復処理しsumます。ただし、値が以前に認識されたサブセットの合計から導出できる場合にのみ、サブセットの合計値が認識されます。つまり、 の任意の反復に対してj、s[j]が 1 の場合にのみ が 1になりs[j - a[i]]ます。最初は空のサブセットのみが認識されるため、最初の反復では のみが認識されs[a[0]]ます。2 回目の反復では、 と が認識さs[a[1]]れs[a[0]+a[1]]ます。3 回目の反復では、 、 、および が認識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 に答える