我使用的解决的动态的问题。
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 of Reference
我哪里做错了吗?
该错误的结果,当您试图访问 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];