替换方程运算符，使和为零

Question

我得到了这样的等式：

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

如何优化替换运算符，使方程之和为零，或者打印⟩-1。我想到了一种算法，但它不是最优的。我有一个想法来暴力破解所有具有复杂性 O(n*2^n) 的案例，但是 (n < 300).

这里是问题的link：http://codeforces.com/gym/100989/problem/M.

Answer 1

我能想到的：

你计算出原方程。这导致 -14。现在您对数字进行排序（考虑到它们的 + 或 -）当等式得出负数时，您会寻找最大的数字来修正等式。当数字太大时，您将跳过它。

orig_eq = -14

排序后：

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

如果等式 orig_eq - 当前数字更接近于零，则循环此和 select 每个数字。

这样你可以select每个数字改变

的符号

Answer 2

你可以用动态规划来解决这个问题。保留所有可能的部分和的映射（映射到达到这个和的最小变化次数），然后一次更新一个数，

这是一个简明的 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 3

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

替换方程运算符，使和为零

Replace operators of equation, so that the sum is equal to zero

algorithm

recursion

dynamic-programming

backtracking