替换等式的运算符,使得总和等于零

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

您可以使用动态编程解决此问题.保留所有可能的部分和的映射(映射到达到此总和的最小更改数),然后一次更新一个数字,

这是一个简洁的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])

理论上,这在最坏的情况下具有指数复杂性(因为部分和的数量在每一步都可以加倍).但是,如果(如此处)给定数字总是(有界)小的整数,则部分和的数量线性增长,并且程序在O(n ^ 2)时间内工作.

稍微优化的版本使用排序数组(小计,成本)而不是字典.可以丢弃太大或太小的部分和(假设所有剩余元素都在-300和+300之间,则不可能最终为0).这大约快两倍,并且是一种更自然的实现,可以移植到比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])

Answer 2

下面是 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);
}