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

Question

这不是家庭作业,我没有钱上学,所以我在高速公路上的收费站工作班次(长时间没有顾客).

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

我使用Collections在Java中实现了一个实现,但这是非常臃肿的代码,即使我能够返回所有集合,加上所需的数字,并告诉函数在第一场比赛时停止.

我对这段代码的问题如下:而不是在2 ^ n时间内运行(这对于没有找到结果的实现是正确的,不是吗？)它在[2 ^(n + 1)]中运行 - 1次; O(2 ^ n)由评论指出.我可以看出为什么我会在更深层次上检查(runningTotal == targetTotal),实际上我自己添加了额外的深度,不是吗？我试图尽可能干净地模拟基本情况,如果你发现任何"代码味道",请告诉我.我一看到(runningTotal +考虑)== targetTotal,我应该立即打破吗？

注意:我不认为这属于"Code Review",因为我在询问特定的代码行,而不是整体方法(如果我需要改变方法,那么就这样吧,我这样做是为了学习).

在这里我的尝试(这是"可通过的"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目标总和不为零，并且不是您拥有的元素。

您调用该函数，这会立即增加计数器，然后到达分叉，该函数调用自身两次（一次考虑元素，一次不考虑元素）。每个调用都会计数 1，因此最终计数器总数为 3。

我没看出这有什么问题...

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

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

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

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