平衡分区（查找两个分区之间的最小一笔一组正整数的）

问题描述

我使用的解决的动态的问题。

I am solving using dynamic problem.

我的 C code是如下：

My C code is below :

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;

}

不过，我收到错误的输出数组= [1,5]。我正在使用的问题7中给出的思路解决参考

But I am getting wrong output for array=[1,5]. I am solving using the idea given in problem 7 ofReference

我哪里做错了吗？

推荐答案

该错误的结果，当您试图访问 J-改编[I] 时，它是否定的。

The error outcomes when you try to access j-arr[i] when it is negative.

在均衡的分区算法，假设整数是负数。所以，请更新您的code是这样的：

In balanced partition algorithm, you assume that integers are nonnegative. So please update your code like this:

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];

这篇关于平衡分区（查找两个分区之间的最小一笔一组正整数的）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！