数组“sum and/or sub”是否为 `x`？

Question

目标

我想编写一个算法（在 C 中）returns TRUE 或 FALSE（1 或 0 ) 取决于输入中给出的数组 A 是否可以“将 and/or sub” 与 x 相加（详见下文）。请注意，A 的所有值都是在 [1,x-1] 之间随机（均匀）采样的整数。

说明和示例

所谓“sum and/or sub”，我的意思是将“+”和“-”放在数组的每个元素前面并求和。我们称这个函数为 SumSub.

int SumSub (int* A,int x)
{
...
}

SumSub({2,7,5},10)

应该returnTRUE为7-2+5=10。您会注意到 A 的第一个元素也可以取负数，因此 A 中元素的顺序无关紧要。

SumSub({2,7,5,2},10)

应该 return FALSE 因为没有办法对 array 的元素进行“求和 and/or 子运算”以达到 x 的值。请注意，这意味着必须使用 A 的所有元素。

复杂度

设n为A的长度。如果必须探索所有可能的正负组合，则问题的复杂度为 O(2^n) 阶。但是，某些组合比其他组合更有可能，因此值得首先探索（希望输出为 TRUE）。通常，需要从最大数中减去所有元素的组合是不可能的（因为 A 的所有元素都小于 x）。此外，如果 n>x，则尝试将 A 的所有元素相加是没有意义的。

问题

我应该如何编写这个函数？

Answer 1

不幸的是，您的问题可以简化为 subset-sum problem，即 NP-Complete。因此无法避免指数解决方案。

Answer 2

不幸的是，即使 x 被限制为值 0，这也是 NP 完全的，所以不要指望多项式时间算法。为了证明这一点，我将对 NP-hard Partition Problem 进行简单归约，它询问是否可以将给定的正整数多重集划分为两个总和相等的部分：

假设我们有一个由 n 个正整数 B_1, ..., B_n 组成的分区问题实例。从此问题创建一个实例，其中 A_i = B_i 每个 1 <= i <= n，并设置 x = 0.

显然，如果将 B 划分为总和相等的 C 和 D 两部分，那么您的问题实例也有一个解决方案：在 C 中的每个数字前放置一个 + ，以及 D 中每个数字前面的 -（或相反）。由于 C 和 D 的和相等，因此该表达式必须等于 0。

OTOH，如果我们刚刚创建的问题实例的解决方案是“是”（真），那么我们可以轻松地将 B 划分为两部分，总和相等：只需将所有正项放在一个部分（例如，C），以及另一部分（例如，D）中的所有否定项（当然没有前面的 -）。既然我们知道表达式的总值为0，那么必然是C中的（正）数之和等于D中的（负）数之和。

因此，对任一问题实例的肯定意味着对另一个问题实例的肯定，这反过来意味着对任一问题实例的否定都意味着对另一个问题实例的否定——也就是说，两个问题实例具有平等的解决方案。因此，如果有可能在多项式时间内解决您的问题，那么也有可能在多项式时间内解决 NP-hard 分区问题，方法是构造上述问题的实例，用您的多时间算法解决它，并报告它给出的结果。

Answer 3

原题的解确实如你所说是指数级的。但是对于 A[] 中数字的给定范围 [1,x-1]，您可以使解多项式。有一个非常简单的动态规划解决方案。

跟单：

时间复杂度：O(n^2*x)

内存复杂度：O(n^2*x)

其中，n=A[]中元素的数量

你需要为此使用动态规划方法

你知道在 [-nx,nx 范围内可以达到的最小、最大范围。创建一个大小为 (n)X(2*n*x+1) 的二维数组。让我们称之为 dp[][]

dp[i][j] = 从 [0..i-1] 中取出 A[] 的所有元素是否有可能得到值 j

所以

dp[10][3] = 1 表示取 A[] 的前 10 个元素，我们可以创建值 3

dp[10][3] = 0 意味着取 A[] 的前 10 个元素我们不能创建值 3

这是一种伪代码：

int SumSub (int* A,int x)
{
    bool dp[][];//set all values of this array 0
    dp[0][0] = true;
    for(i=1;i<=n;i++) {
        int val = A[i-1];
        for(j=-n*x;j<=n*x;j++) {
            dp[i][j]=dp[ i-1 ][ j + val ] | dp[ i-1 ][ j - val ];
        }
    }
    return dp[n][x];
}

数组“sum and/or sub”是否为 `x`？

Does the array “sum and/or sub” to `x`?

c

arrays

algorithm

performance

complexity-theory