合計が、私はこのような方程式を与えてるゼロ

Question

に等しくなるように、式の演算子を置き換えます

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

式の合計が等しくなるように、どのように最適に、演算子を置き換えることができますゼロ、または印刷-1。私は1つのアルゴリズムを考えますが、最適ではありません。私は、複雑さがすべてO(n*2^n)だが、(n < 300)のすべてのケースをブルートフォースする考えがあります。

ここに問題のリンク：http://codeforces.com/gym/100989/problem/Mがあります。あなたは元の方程式を計算

：何を私は考えることができる

Answer 1

は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

。これは-14になります。 数値をソートする（+または - を考慮に入れて） 方程式の結果が負の数になると、最大の数を探して方程式を修正します。数字が大きすぎる場合は、スキップします。

ソート後

orig_eq = -14

：

-4、-4、-4、-2、-2、1、1

次ループこの上及び各番号を選択した場合方程式orig_eq - 現在の数はゼロに近い。

この方法であなたは、動的プログラミングでこれを解決することができ

Answer 3

の符号を変更するには、各番号を選択することができます。で

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

：ここでは簡潔なPythonのソリューションがありますすべての可能な部分和（変更の最小数へのマッピングこの合計に到達する）のマップを維持し、その後、一度それを1つの番号を更新し、

この理論では、最悪の場合に指数関数的な複雑さがあります（各ステップで部分和の数が2倍になる可能性があるため）。しかし、（ここでのように）与えられた数が常に小（int）であれば、部分和の数は線形に増加し、プログラムはO（n^2）時間で動作します。

さらに最適化されたバージョンでは、dictの代わりにソートされた配列（小計、コスト）が使用されます。大きすぎるか小さすぎる部分和を捨てることができます（残りの要素のすべてが-300と+300の間であると仮定すると、0に終わることは不可能になります）。これは約2倍の速さで実行され、Pythonよりも低速な言語に移植することで最大のスピードを実現します。ここで

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