algorithm - 将一个数组最佳地划分为两个子数组，使两个子数组中的元素之和相同

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

您正在尝试解决 Partition Problem ;即将整数分成两个子集，其总和相同，并将正号分配给一个子集中的整数，将负号分配给另一子集中的整数。

在您的特定问题中，您对整数的数量和这些整数的值都有一个下限。您可以将标准动态算法方法与包含/排除方法一起应用；即通过考虑未使用这些整数中的最后一个的情况，找到总和为 i 的前 n 个整数的子集(因此您需要第一个n-1 整数总和为 i)及其使用位置(前 n-1 整数总和为 i 的子集- val(n)).