Wymień operatorów równania, tak że suma jest równa zeru

Question

mam podane równanie jak ten:

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

Jak mogę optymalnie zastąpić operatorów, tak że suma równania jest równa zero lub wydrukuj -1. Myślę o jednym algorytmie, ale nie jest on optymalny. Mam pomysł na brutalne skompletowanie wszystkich przypadków ze złożonością O(n*2^n), ale (n < 300).

Oto link do problemu: http://codeforces.com/gym/100989/problem/M.

Answer 1

Oto implementacja w 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

Co mogę myśleć:

Obliczasz oryginalne równanie. Daje to w -14. Teraz sortujesz liczby (biorąc pod uwagę ich + lub -) Gdy równanie daje liczbę ujemną, szukasz największych liczb, aby naprawić równanie. Gdy liczba jest zbyt duża, pomijasz ją.

orig_eq = -14

Po sortowaniu:

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

zapętlić przez to i wybrać każdy numer Kiedy równanie orig_eq - aktualna liczba jest bliższa zeru.

W ten sposób można wybrać każdą liczbę, aby zmienić znak

Answer 3

można rozwiązać ten z programowania dynamicznego. Przechowywać mapę wszystkich możliwych sum częściowych (mapowanie z minimalną ilością zmian do osiągnięcia tej kwoty), a następnie zaktualizować jeden numer na raz,

Oto zwięzły rozwiązanie Python:

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]) 

W teoria ta ma wykładniczą złożoność w najgorszym przypadku (ponieważ liczba częściowych sum może się podwoić na każdym kroku). Jeśli jednak (jak tutaj) podane liczby są zawsze (ograniczone) małymi intami, to liczba sum cząstkowych rośnie liniowo, a program działa w czasie O (n^2).

Nieco bardziej zoptymalizowana wersja wykorzystuje posortowaną tablicę (suma częściowa, koszt) zamiast dyktowania. Można odrzucić częściowe kwoty, które są zbyt duże lub zbyt małe (co uniemożliwia osiągnięcie wartości 0, przy założeniu, że wszystkie pozostałe elementy mieszczą się w zakresie od -300 do +300). Działa to mniej więcej dwa razy szybciej i jest bardziej naturalną implementacją, która umożliwia przeniesienie do języka niższego poziomu niż Python dla maksymalnej prędkości.

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])