1

動的問題法を使って解いています。

私のCコードは以下の通りです：

int balanced_partition( int arr[] , int n){

    int i,j;
    int sum=0;
    for(i=0;i<n;i++)
        sum+=arr[i];

    int p[n+1][sum+1];
    for(i=0;i<n+1;i++){
            for(j=0;j<sum+1;j++){
                    if(i==0)
                            p[0][j]= 0;
                    else if(j==0)
                            p[i][0]=1;
                    else{
                            if( (i-1>=0 && p[i-1][j]==1) ||  ( i-1>=0 && j-arr[i]>=0 && p[i-1 [j-arr[i]]==1) )
                                    p[i][j]=1;
                            else
                                    p[i][j]=0;
                            }
                    }
            }

    int min=INT_MAX;
    int half_sum=sum/2;
    for(i=half_sum;i>=0;i--)
            if(p[n][half_sum-i]==1 && min >(half_sum-i) ){
                    min = half_sum-i;
                    }
    return min;

}

しかし、array=[1,5]の出力が間違っています。参考文献の問題7で与えられたアイデアを使用して解決しています

私が間違っているところは？

4

2 に答える 2

2

j-arr[i]負のときにアクセスしようとすると、エラーが発生します。

平衡分割アルゴリズムでは、整数が非負であると想定します。したがって、次のようにコードを更新してください。

if(arr[i] <= j)
     p[i][j] = max( p[i-1][j] , p[i-1][j-arr[i]] );
else
     p[i][j] = p[i-1][j];
于 2013-02-14T15:15:27.193 に答える
0

質問に答えるのが遅いことは知っていますが、コードで確認できる問題は、変数iの範囲が[0、n]（nを含む）であるという事実によるものです。

コードスニペット：

if( (i-1>=0 && p[i-1][j]==1) ||  ( i-1>=0 && j-arr[i]>=0 && p[i-1 [j-arr[i]]==1) )

配列のサイズはn 、つまり0からn-1であり、 iの範囲は[ 0、n]であるため、 i =nのa[n]はArrayIndexOutOfBoundsExceptionをスローするため、 j--arr[i-1]を使用する必要があります。 jの代わりにあなたのコード--arr[i]。

if( (i-1>=0 && p[i-1][j]==1) ||  ( i-1>=0 && j-arr[i-1]>=0 && p[i-1 [j-arr[i-1]]==1) )
于 2014-04-13T23:48:46.737 に答える