将数组最佳地划分为两个子阵列,以使两者中的元素总和相同

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

您正在尝试解决分区问题 ; 即将整数划分为两个子集,其总和相同,并将正符号分配给一个子集中的整数,将负符号分配给另一个子集中的整数.

在您的特定问题中,您对整数的数量和这些整数的值都有一个下限.您可以使用包含/排除方法应用标准动态算法方法; 即找到的第一个子集n,总结为整数i,通过考虑其中最后这些整数不使用的情况下(所以你需要第一个的子集n-1整数相加来i),并在那里使用(第一子集n-1的整数求和i - val(n)).