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

Question

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

给定一个整数序列，为每个整数分配一个符号（+ 或 -），使总和等于 0。对于所有序列，保证它们可以加到 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 的前提下）？

标签： algorithmsortingintegersequence

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这导致 summation = 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;
}