16

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

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

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

我对这段代码的问题如下：而不是在 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;
}
4

1 回答 1

2

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

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

我看不出这有什么不妥...

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

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

于 2012-08-20T05:50:58.190 回答