C++ 子集总和 2^n/递归错误/澄清

Question

这不是家庭作业，我没有钱上学，所以我一边在高速公路上的收费站轮类工作，一边自学(长夜，顾客很少)。

我正在尝试实现一个简单的子集求和算法，该算法给定一个整数数组，返回其总和等于所需总和的子集，并报告找到它需要多少次调用。

我在 Java 中使用 Collections 进行了实现，但那是非常臃肿的代码，即使我能够返回所有集合加起来达到所需的数字，并告诉函数是否在第一次匹配时停止。

我对这段代码的问题如下:而不是在 2^n 时间内运行(当没有找到结果时，这对于这样的实现是正确的，不是吗？)它在 [2^(n+1 )]-1次; O(2^n) 正如评论所指出的那样。我可以明白为什么我检查 (runningTotal == targetTotal) 比我能做的更深层次，本质上是我自己增加了额外的深度，不是吗？我试图尽可能干净地模拟基本案例，如果您检测到任何“代码气味”，请告诉我。我应该一看到(runningTotal + 考虑)== targetTotal 就崩溃吗？

注意:我认为这不属于“代码审查”，因为我询问的是特定代码行，而不是整体方法(如果我需要更改方法，就这样吧，我这样做是为了学习)。

这是我的尝试(除了上面提到的缺乏优化之外，这是“合格”的 C/C++ 吗？):

#include <iostream>
using namespace std;
bool setTotalling(int chooseFrom[], int nChoices, int targetTotal,
    int chooseIndex, int runningTotal, int solutionSet[], int &solutionDigits,
    int &nIterations) {
  nIterations++;
  if (runningTotal == targetTotal) {
    return true;
  }
  if (chooseIndex >= nChoices) {
    return false;
  }
  int consider = chooseFrom[chooseIndex];
  if (setTotalling(chooseFrom, nChoices, targetTotal, chooseIndex + 1,
      runningTotal + consider, solutionSet, solutionDigits, nIterations)) {
    solutionSet[solutionDigits++] = consider;
    return true;
  }
  if (setTotalling(chooseFrom, nChoices, targetTotal, chooseIndex + 1,
      runningTotal, solutionSet, solutionDigits, nIterations)) {
    return true;
  }
  return false;
}
void testSetTotalling() {
  int chooseFrom[] = { 1, 2, 5, 9, 10 };
  int nChoices = 5;
  int targetTotal = 23;
  int chooseIndex = 0;
  int runningTotal = 0;
  int solutionSet[] = { 0, 0, 0, 0, 0 };
  int solutionDigits = 0;
  int nIterations = 0;
  cout << "Looking for a set of numbers totalling" << endl << "--> "
      << targetTotal << endl << "choosing from these:" << endl;
  for (int i = 0; i < nChoices; i++) {
    int n = chooseFrom[i];
    cout << n << ", ";
  }
  cout << endl << endl;
  bool setExists = setTotalling(chooseFrom, nChoices, targetTotal, chooseIndex,
      runningTotal, solutionSet, solutionDigits, nIterations);
  if (setExists) {
    cout << "Found:" << endl;
    for (int i = 0; i < solutionDigits; i++) {
      int n = solutionSet[i];
      cout << n << ", ";
    }
    cout << endl;
  } else {
    cout << "Not found." << endl;
  }
  cout << "Iterations: " << nIterations << endl;
}
int main() {
  testSetTotalling();
  return 0;
}

Answer 1

关键是如何计算“迭代”。假设您有一个简单的情况，n=1 的目标总和不为零，而不是您拥有的元素。

您调用该函数，这会立即增加计数器，然后您到达 fork 处，该函数调用自身两次(一次考虑元素，一次不考虑元素)。这些调用中的每一个都将计为 1，因此您最终的总计数器为 3。

我看不出有什么问题...

如果剩余选择的数量为零，您可以添加一个特殊检查来重复测试并避免调用，但这需要重复检查。仅在递归调用位置进行结束检查不会考虑可以直接使用零选择调用函数。基本上你是“内联”级别 0...但是为什么停在级别零而不内联级别 1？

如果您正在寻找加速，请注意(假设所有元素都是非负数)如果您知道添加所有剩余的可用数字仍然不足以达到目标，那么您可以避免检查所有可能的子集. 通过计算从给定索引到可用元素列表末尾的所有剩余数字的总和(这是一个 O(n) 计算)，您可以节省(2^remaining)次迭代。 此外，如果当前的总和已经太大，那么考虑添加其他元素也没有意义。

if (targetTotal > runningTotal)
    return false; // We already passed the limit
if (targetTotal - runningTotal > sumOfAllFrom[choseIndex])
    return false; // We're not going to make it

如果你还按降序对元素进行排序，上面的优化可以节省很多。