2

我想实现平衡分区问题并使用反向指针获取子集的元素。

我有一个关于反向指针的问题：

在麻省理工学院的动态编程练习题 Nr 的帮助下。7和这个示例代码，我设法在处理中获得了一个工作程序（因为我是一个编程新手......）。

现在我希望能够获得两个子集的元素。

在 MIT Video 中解释说，这可以“使用维护反向指针的标准技巧”来实现。

有谁知道如何做到这一点？

int N=4;
int[] Weights=new int[N];
int Deviation=5;


void setup()
{
 for(int i=0;i<N;i++)
{
 Weights[i]=10+int(random(-Deviation, Deviation));
 println(i+"   "+Weights[i]);
} 

println("-------------------");

BalancedPartition(Weights,N);

}


void 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 ans = 0;
    int diff = 1000000000;


    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;


                 }

            }

        }
    }
println("Sum Set 1: "+ans+"        Sum Set 2: "+(sum-ans)+"          Difference: "+abs(ans-(sum-ans)) );



}
4

0 回答 0