algorithm - 通过分配符号来检查一系列整数总和是否为 0 的最有效算法是什么？

Question

我想以有效的方式解决以下问题:

给定一个整数序列，为每个整数分配一个符号(+ 或 -)，使得总和为零。对于所有序列，保证它们可以相加为 0。

示例:

原始序列:1, 3, 5, 2, 1, 4

输出:+5、-4、-3、+2、-1、+1

想法:

一个接一个地尝试每一种组合。对于看起来像这样的 6 个数字(只是符号):

++++++
+++++-
++++-+
++++--
and so on...

首先尝试对序列进行排序。将 + 分配给第一个数字，然后减去直到你是负数，然后再次添加直到你是正数。

first sort: 
5, 4, 3, 2, 1, 1
+5 (sum = 5) 
+5, -4 (sum = 1) 
+5, -4, -3 (sum = -2)
+5, -4, -3, +2 (sum = 0) 
+5, -4, -3, +2, -1 (sum = -1)
+5, -4, -3, +2, -1, +1 (sum = 0)

有没有更好的方法来解决这个问题？第二个是否有意义，或者是否有可能不起作用(在您可以将 seq 加起来为 0 的前提下)？

Answer 1

如果您的第一个想法是:
你的第一个想法是一个接一个地尝试每一种可能的组合并检查求和肯定会奏效，但问题是复杂性会非常高。为此，我们可以简单地这样做:

bool recursion(int pos, int n, int sum, vector<int>&sequence) {
  if (pos == n) {
     if (sum == 0) return true;
     else return false;
   }
   bool resultTakingPositive =  recursion(pos + 1, n, sum + sequence[pos], sequence);
   bool resultTakingNegative =  recursion(pos + 1, n, sum - sequence[pos], sequence);
   if (resultTakingPositive || resultTakingNegative) return true;
   else return false;
}

如果总共有 n 个整数，则此解决方案的时间复杂度为 O(2^n)。因为在每个位置，都有两个选择:

• 求和+ve 值。
• 求和-ve值。

而且，我们必须对每个 n 整数做出选择。因此，n 乘以 2 导致 O(2^n) 时间复杂度。

如果您有第二个想法:
您正在尝试首先以非递增顺序对序列进行排序，并将 +ve 符号分配给第一个数字，然后减去直到得到负数，然后再次添加直到得到正数。不幸的是，这种贪心的方法并不总是奏效。例如:
在一个序列中:5, 4, 4, 3, 2
如果我们尝试这种方法，我们将得到:+5 -4 -4 +3 +2 导致求和 = 2。
但是，我们可以通过执行以下操作使总和为零:+5 +4 -4 -3 -2。

高效方法:
我们可以在上面的递归解决方案中使用内存并进行简单的修改，以便在状态为 pos 和 sum 的情况下允许正索引。这也称为动态规划。为此，pos * sum 的最高可能值应该较小，以便使用二维数组将它们的状态缓存在内存中。因此，时间和空间复杂度均为 O(n * sum)。这种使用 C++ 代码的方法示例如下:

#include<bits/stdc++.h>
using namespace std;

bool recursion(int pos, int n, int sum, vector<int>&sequence,int &baseSum,  vector< vector<int> >&dp) {
  if (pos == n) {
     if (sum == baseSum) return true;
     else return false;
  }
  if (dp[pos][sum] != -1) return dp[pos][sum];
  bool resultTakingPositive =  recursion(pos + 1, n, sum + sequence[pos], sequence, baseSum, dp);
  bool resultTakingNegative =  recursion(pos + 1, n, sum - sequence[pos], sequence, baseSum, dp);
  dp[pos][sum] = (resultTakingPositive || resultTakingNegative);
  return dp[pos][sum];
}

int main() {
  vector<int>sequence;
  int n, baseSum = 0;
  scanf("%d",&n);
  for (int i = 1; i <= n; i++) {
     int x;
     scanf("%d",&x);
     sequence.push_back(x);
     baseSum += x;
  }
  vector< vector<int> >dp(n, vector<int>(2*baseSum + 1, -1));
  cout<<recursion(0, n, baseSum, sequence, baseSum, dp)<<endl;
  return 0;
}

现在，如果我们想跟踪用于构成和 0 的符号，我们可以通过分析递归调用来实现，如下所示:

#include<bits/stdc++.h>
using namespace std;

bool recursion(int pos, int n, int sum, vector<int>&sequence,int &baseSum, vector< vector<int> >&dp) {
  if (pos == n) {
     if (sum == baseSum) return true;
     else return false;
  }
  if (dp[pos][sum] != -1) return dp[pos][sum];
  bool resultTakingPositive =  recursion(pos + 1, n, sum + sequence[pos], sequence, baseSum, dp);
  bool resultTakingNegative =  recursion(pos + 1, n, sum - sequence[pos], sequence, baseSum, dp);
  dp[pos][sum] = (resultTakingPositive || resultTakingNegative);
  return dp[pos][sum];
}

void printSolution(int pos, int n, int sum, vector<int>&sequence,int &baseSum, vector< vector<int> >&dp) {
  if (pos == n) {
    cout<<endl;
    return;
  }
  bool resultTakingPositive =  recursion(pos + 1, n, sum + sequence[pos], sequence, baseSum, dp);
  if (resultTakingPositive == true) {
     cout<< "+ ";
     printSolution(pos + 1, n, sum + sequence[pos], sequence, baseSum, dp);
  } else {
    cout<< "- ";
    printSolution(pos + 1, n, sum - sequence[pos], sequence, baseSum, dp);
  }
}

int main() {
  vector<int>sequence;
  int n, baseSum = 0;
  scanf("%d",&n);
  for (int i = 1; i <= n; i++) {
     int x;
     scanf("%d",&x);
     sequence.push_back(x);
     baseSum += x;
  }
  vector< vector<int> >dp(n, vector<int>(2*baseSum + 1, -1));
  if (recursion(0, n, baseSum, sequence, baseSum, dp)) { // if possible to make sum 0 then
      printSolution(0, n, baseSum, sequence, baseSum, dp);
   }
   return 0;
}