16

これは宿題ではありません。学校に行くお金がないので、高速道路の料金所でシフトを組みながら独学しています (顧客が少ない長い夜)。

整数の配列を指定すると、その合計が目的の合計に等しいサブセットを返し、それを見つけるのにかかった呼び出しの数を報告する単純なサブセット合計アルゴリズムを実装しようとしています。

コレクションを使用してJavaで実装しましたが、すべてのセットを合計して目的の数に戻すことができたとしても、最初の一致で停止するかどうかを関数に指示できたとしても、それは非常に肥大化したコードでした。

このコードで私が抱えている問題は次のとおりです: 2^n 時間で実行するのではなく (結果が見つからない場合、そのような実装では正しいですよね?)、[2^(n+1)] で実行されます。 1回; コメントで指摘された O(2^n) 。(runningTotal == targetTotal) を自分でチェックできるよりも深いレベルでチェックし、本質的に自分で余分な深さを追加する理由がわかりますね。基本ケースをできるだけきれいにモデル化しようとしていましたが、「コードのにおい」を検出した場合はお知らせください。(runningTotal + think) == 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ゼロではなく、あなたが持っている要素ではない合計を対象とする単純なケースがあるとします。

関数を呼び出すと、すぐにカウンターがインクリメントされ、分岐に到達すると、関数は自分自身を 2 回呼び出します (1 回は要素を考慮し、もう 1 回は要素を考慮しません)。これらの呼び出しはそれぞれ 1 カウントされるため、合計カウンターは 3 になります。

これには何も問題はありません...

残りの選択肢の数がゼロの場合、テストを繰り返して呼び出しを回避する特別なチェックを追加できますが、これにはチェックを繰り返す必要があります。再帰呼び出しの場所でのみ終了チェックを行うと、関数がゼロチョイチで直接呼び出される可能性が考慮されません。基本的に、レベル 0 を「インライン化」していますが、レベル 0 で停止し、レベル 1 もインライン化しないのはなぜですか?

スピードアップを探している場合は、(すべての要素が非負であると仮定して) 残りの使用可能なすべての数値を追加してもターゲットに到達するのに十分ではないことがわかっている場合は、可能なすべてのサブセットのチェックを回避できることに注意してください。特定のインデックスから使用可能な要素のリストの最後までの残りのすべての数値の合計を 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 に答える