>我正在使用动态问题解决。
我的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;
}
但是我得到的数组=[1,5]输出错误。我正在使用问题 7 中给出的想法来解决参考
我哪里做错了?
当您尝试访问错误时,错误结果为负数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];
我知道
回答这个问题已经很晚了,但我可以在代码中看到的问题是由于变量 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] 所以 a [n] for i = 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) )