在集合中查找整数符号组合以使集合总和为 0 的算法

Question

给定 S 的 n ] 正整数，我们想知道是否可以找到S中每个数的符号组合（+或-）使得S之和为0.

如何有效解决这个问题？基于类似的问题，我想某种动态规划是有序的。有没有关于这个特定问题的文献（我很难找到它）。

我猜这类似于子集和问题。但是，现在我们必须使用整个集合，对于每个整数 s_i 我们可以包括-s_i 或 +s_i，但不是两者。

Answer 1

这道题的解法涉及子集和问题

如果存在一种求和为数组总和的一半的方法，那么我们可以将所有这些数字都设置为负数。其余的数字将是积极的。由于这些子集中的每一个总和为总和的一半，因此它们各自的总和将为 0。

这里是c++中的代码：

#include<stdio.h>

int arr[] = {1, 2, 2, 3, 4};
int n = 5; // size of arr
int sum = 0;

// dp array only needs to be [n + 1][total sum + 1] big
bool dp[30][100];
inline void subset_sum(){
    for (int i = 0; i <= sum; i++)
        dp[0][i] = false;

    for (int i = 0; i <= n; i++)
        dp[i][0] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum; j++) {
            dp[i][j] = dp[i - 1][j];
            if (arr[i - 1] <= j)
                dp[i][j] |= dp[i - 1][j - arr[i - 1]];
        }
    }
}
int main(){
    for (int i = 0; i < n; i++)
        sum += arr[i];

    // run subset sum dp using a bottom-up approach
    // True = sum is possible, False = not possible
    subset_sum();

    int max_half;
    for (int i = sum / 2; i>=1; i--){
        if (dp[n][i]){ // it is possible to sum to i using values in arr
            max_half = i;
            break;
        }
    }

    // output will be the closest sum of positives
    // and negatives to 0
    printf("%d\n", 2 * max_half - sum);

    return 0;
}

此代码的输出将是集合中最接近 0 的正数和负数组合的总和。

2 * max_half - sum 可以从 max_half - (sum - max_half) 导出，这将是我们减去其余数字的最佳总和。

以下是不同数字集及其各自输出的一些示例：

设置：{1, 2, 2, 3, 4}，输出：0.

设置：{1, 1, 1, 1, 1}，输出：-1.

设置：{5, 2, 6, 8, 9, 2}，输出：0.

设置：{1, 50}，输出：-49.

子集和问题网上有many explanations，这里就不解释了

这段代码的时间复杂度为O(n * sum)，space复杂度为O(n * sum)。

也可以通过使用一维 dp 数组牺牲一些时间复杂度来提高 space 复杂度。

Answer 2

鉴于问题似乎是 NP 完全的，使用 SAT、MILP、CP 或 ASP 求解器是最佳选择，因为这些都是为解决这类问题而量身定制的。

解决方案

这是一个使用 ASP（答案集编程）的解决方案。

给定一个文件instance.lp:

value(12).
value(12).
value(1).
value(2).
value(3).
value(5).
value(6).
value(7).

和文件 encoding.lp:

% every value can be positive (or not)
{pos(X)} :- value(X).

% fail if the sum is not 0
:- not 0 = #sum {V : pos(V); -V : not pos(V), value(V)}.

% format output
#show pos/1.
#show neg(V) : not pos(V), value(V).

问题可以使用clingo解决， potassco 工具集的 ASP 求解器（可通过 conda、pip、Ubuntu 包管理器等轻松安装）。

通话中：

clingo instance.lp encoding.lp

给你结果：

Answer: 1
pos(1) pos(2) pos(3) pos(5) pos(7) neg(6) neg(12)

您可以列举所有可能的解决方案：

clingo instance.lp encoding.lp 0

给你

Answer: 1
pos(1) pos(2) pos(3) pos(5) pos(7) neg(6) neg(12)
Answer: 2
pos(2) pos(3) pos(6) pos(7) neg(5) neg(1) neg(12)
Answer: 3
pos(5) pos(6) pos(7) neg(3) neg(2) neg(1) neg(12)
Answer: 4
pos(12) pos(1) pos(2) pos(3) neg(7) neg(6) neg(5)
Answer: 5
pos(12) pos(6) neg(7) neg(5) neg(3) neg(2) neg(1)
Answer: 6
pos(12) pos(1) pos(5) neg(7) neg(6) neg(3) neg(2)

ASP

使用ASP解决问题的好处是：

beeing 易于维护（问题描述非常简短，易于阅读）
非常快（基于 SAT 和 CDNL）
声明式（你只描述问题，而不是如何解决）
可通过其他约束轻松扩展
也能做各种优化（比如优化最大子集求和）

编辑也可以复制粘贴两个文件的内容自己上网查看结果，使用js编译clingohere

在集合中查找整数符号组合以使集合总和为 0 的算法

Algorithm to find combination of signs of integers in a set such that the set sums to 0

algorithm

complexity-theory

dynamic-programming

np