这个问题的最佳算法是什么？

Question

考虑一组A = a1，a2 ,. 。 。 ，a-1，n个项中的一个，其中每个ai是正整数，值Z是以下问题的输入：是否有子集A0 = {ai1，ai2，... 。 。 ，aik}⊆这样Z =✷ai1✷ai2✷。 。 。 ✷在哪里✷是+或 - ？

例如，如果给定输入为{3,5,4}且Z = 2，则我们可以得到2 = -3 + 5。虽然我们没有Z = 10的任何组合。对于Z = 6，我们有6 = -3 + 5 + 4的组合。

编写一个递归函数IsSummable（Z，A）来确定是否可以找到

子集A0⊆A使得值Z可以通过仅使用两个操作+或 - 的元素A0的组合来实现。

Answer 1

这是子集和的变化，其可以使用动态编程在伪多项式时间中求解

这里是O（n * W）解：其中w是abs的总和（a [i]）

1. 让我们说dp[i][j] = 1，如果我们可以在考虑i项后获得j的总和，否则为0
2. 基本情况：dp[0][0] = 1
3. 另一种情况，当考虑元素i时，可以说它的值是[i]： 我们可以从国家达到一些州dp [i] [j]： dp[i-1][j]（跳过当前元素） dp[i-1][j-a]（带+符号的usecurrent元素） dp[i-1][j+a]（带有 - 符号的usecurrent元素）

因此解决方案如下所示：

dp[0][0]=1

for(int i=1; i<=n; i++)
for(int j=-W; j<=W; j++)
dp[i][j]|=dp[i-1][j] | dp[i-1][j-a[i]] | dp[i-1][j+a[i]]

return dp[n][Z]