バランス パーティションの問題を実装し、バックポインターを使用してサブセットの要素を取得したいと考えています。
バックポインターについて質問があります。
MIT の Dynamic Programming Practice Problems Nr.の助けを借りて。7 とこのサンプル コードを使用して、Processing で動作するプログラムを取得することができました (私はプログラミング初心者なので...)。
ここで、両方のサブセットの要素を取得できるようにしたいと考えています。
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)) );
}