Schwierigkeiten beim Verständnis der Logik der ausgeglichenen Partitionierung

Question

Ich war ein Problem der ausgewogenen Partitionierung von this link lösen. In dieser Frage müssen wir das Array in gleiche Teile teilen, so dass der Unterschied zwischen ihrer Summe am geringsten ist. Also, die Lösung, die ich herausgefunden habe, berücksichtigt alle Fälle, ob ein Element in einer Gruppe enthalten ist oder nicht, bedeutet, dass wir alle 2^n Fälle versuchen müssen.

Ich kam mit einer Lösung, die das Array mit Bit-Manipulation geteilt und ich bekomme nicht die Logik. Ich poste den Code unten. Jemand sagt mir bitte, wie teilt er das Array auf?

#include<bits/stdc++.h> 
using namespace std; 
#define N 11 

void solve(int a[N]) 
{ 
    long long x,y,v1,v2,res,i,j; 
    long long val=1<<N; 
    res=INT_MAX; 
    for(i=0;i<val;i++) 
    { 
     x=y=v1=v2=0; 
     for(j=0;j<N;j++) 
     { 
      if(i & (1<<j)) 
      { 
       x++; 
       v1+=a[j]; 
      } 
      else 
      { 
       y++; 
       v2+=a[j]; 
      } 
     } 
     if(abs(x-y)<=1) res=min(res,abs(v1-v2)); 
    } 
    cout<<res<<endl; 
} 
int main() 
{ 
    int a[] = {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}; 
    solve(a); 
    return 0; 
} 

Answer 1

zu optimieren Sie das erste und das letzte Element jeder cicle Teilmenge summieren könnten versuchen, und so vermeiden, dass alle Elemente Nummer Ihres Untergruppe haben cicling aber nur für eine Anzahl von Malen cicling gleich der Hälfte Ihre Teilmenge Größe ..

In Ihrem Beispiel die externe Zyklus Iterationen gleich bleiben, während die internen von 2 eigentuemlichen sind:

(for(j=0; j<(N/2); j++) 

und die Summe Ihres gruppierte Subsetelemente:

v(1|2)+=(a[j] + a[N-j]);