Ersetzen Betreiber der Gleichung, so dass die Summe auf Null

Question

gleich ich die Gleichung wie diese gegeben habe:

n = 7 
1 + 1 - 4 - 4 - 4 - 2 - 2 

Wie kann ich Bediener optimal ersetzen, so dass die Summe der Gleichung gleich Null oder Drucken -1. Ich denke an einen Algorithmus, aber es ist nicht optimal. Ich habe eine Idee, alle Fälle mit Komplexität O(n*2^n), aber (n < 300) bruteforce.

Hier ist der Link des Problems: http://codeforces.com/gym/100989/problem/M.

Answer 1

Hier ist die Implementierung in C++:

unordered_map <int, int> M, U; 
unordered_map<int, int>::iterator it; 
int a[] = {1, -1, 4, -4}; 

int solve() { 
    for(int i = 0; i < n; ++i) { 
     if(i == 0) M[a[i]] = 1; 
     else { 
      vector <pair <int, int>> vi; 
      for(it = M.begin(); it != M.end(); ++it) { 
       int k = it->first, d = it->second; 
       vi.push_back({k + a[i], d}); 
       vi.push_back({k - a[i], d + 1}); 
      } 
      for(int j = 0; j < vi.size(); ++j) M[vi[j].first] = MAXN; 
      for(int j = 0; j < vi.size(); ++j) { 
       M[vi[j].first] = min(M[vi[j].first], vi[j].second); 
      } 
     } 
    } 
    return (M[0] == 0 ? -1 : M[0] - 1); 
} 

Answer 2

Was kann ich mir vorstellen:

Sie die ursprüngliche Gleichung berechnen. Dies ergibt -14. Jetzt sortieren Sie die Zahlen (unter Berücksichtigung ihrer + oder -) Wenn die Gleichung eine negative Zahl ergibt, suchen Sie nach den größten Zahlen, um die Gleichung zu beheben. Wenn eine Zahl zu groß ist, überspringen Sie sie.

orig_eq = -14

Nach dem Sortieren:

-4, -4, -4, -2, -2, 1, 1

Sie Schleife über diese und wählen jede Zahl, wenn die Gleichung orig_eq - aktuelle Zahl ist näher bei Null. Auf diese Weise

Sie können jede Nummer wählen Sie das Zeichen der

Answer 3

ändern Sie diese mit dynamischer Programmierung lösen können. Halten Sie eine Karte aller möglichen Teilsummen (Abbildung auf die minimale Anzahl von Änderungen, diese Summe zu erreichen), und dann aktualisieren sie eine Nummer zu einem Zeitpunkt,

Hier ist eine kurze Python Lösung:

def signs(nums): 
    xs = {nums[0]: 0} 
    for num in nums[1:]: 
     ys = dict() 
     for d, k in xs.iteritems(): 
      for cost, n in enumerate([num, -num]): 
       ys[d+n] = min(ys.get(d+n, 1e100), k+cost) 
     xs = ys 
    return xs.get(0, -1) 

print signs([1, 1, -4, -4, -4, -2, -2]) 

In Theorie hat im schlimmsten Fall exponentielle Komplexität (da sich die Anzahl der Partialsummen bei jedem Schritt verdoppeln kann). Wenn jedoch (wie hier) die gegebenen Zahlen immer (begrenzt) kleine Inte sind, dann wächst die Anzahl der Teilsummen linear, und das Programm arbeitet in O (n^2) -Zeit.

Eine etwas optimierte Version verwendet ein sortiertes Array von (Zwischensumme, Kosten) anstelle eines Diktats. Man kann Teilmengen, die zu groß oder zu klein sind, verwerfen (was es unmöglich macht, bei 0 zu enden, vorausgesetzt, dass alle verbleibenden Elemente zwischen -300 und +300 liegen). Dies läuft ungefähr doppelt so schnell ab und ist eine natürlichere Implementierung, um für eine maximale Geschwindigkeit in eine Sprache auf niedrigerer Ebene als Python zu portieren.

def merge(xs, num): 
    i = j = 0 
    ci = 0 if num >= 0 else 1 
    cj = 0 if num < 0 else 1 
    num = abs(num) 
    while j < len(xs): 
     if xs[i][0] + num < xs[j][0] - num: 
      yield (xs[i][0] + num, xs[i][1] + ci) 
      i += 1 
     elif xs[i][0] + num > xs[j][0] - num: 
      yield (xs[j][0] - num, xs[j][1] + cj) 
      j += 1 
     else: 
      yield (xs[i][0] + num, min(xs[i][1] + ci, xs[j][1] + cj)) 
      i += 1 
      j += 1 
    while i < len(xs): 
     yield (xs[i][0] + num, xs[i][1] + ci) 
     i += 1 

def signs2(nums): 
    xs = [(nums[0], 0)] 
    for i in xrange(1, len(nums)): 
     limit = (len(nums) - 1 - i) * 300 
     xs = [x for x in merge(xs, nums[i]) if -limit <= x[0] <= limit] 
    for x, c in xs: 
     if x == 0: return c 
    return -1 

print signs2([1, 1, -4, -4, -4, -2, -2])