समीकरण के ऑपरेटरों बदलें, ताकि योग शून्य

Question

के बराबर है मैं इस तरह के समीकरण को देखते हुए कर रहा हूँ:

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

मैं कैसे बेहतर, ऑपरेटरों की जगह ले सकता है, ताकि समीकरण की राशि के बराबर है शून्य, या प्रिंट -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]) 

में सिद्धांत में सबसे बुरी स्थिति में घातीय जटिलता है (क्योंकि आंशिक रकम की संख्या प्रत्येक चरण में दोगुनी हो सकती है)। हालांकि, अगर (यहां के रूप में) दिए गए नंबर हमेशा छोटे स्याही होते हैं, तो आंशिक रकम की संख्या रैखिक रूप से बढ़ती है, और कार्यक्रम ओ (एन^2) समय में काम करता है।

कुछ हद तक अधिक अनुकूलित संस्करण एक dict के बजाय क्रमबद्ध सरणी (subtotal, लागत) का उपयोग करता है। कोई आंशिक रकम छोड़ सकता है जो बहुत बड़े या बहुत छोटे होते हैं (यह मानते हुए 0 पर समाप्त होना असंभव हो जाता है कि शेष शेष तत्व -300 और +300 के बीच हैं)। यह लगभग दोगुनी तेजी से चलता है, और अधिकतम गति के लिए पायथन की तुलना में निम्न-स्तर की भाषा में बंदरगाह के लिए एक अधिक प्राकृतिक कार्यान्वयन है।

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