3

これは、指定されたセットとターゲット値からtrueまたはfalseを取得するソリューションの1つです。

bool subsetSumExists(Set<int> & set, int target) {
    if (set.isEmpty()) {
        return target == 0;
    } else {
        int element = set.first();
        Set<int> rest = set - element;
        return subsetSumExists(rest, target)
        || (subsetSumExists(rest, target- element));
    }
}

ただし、このソリューションはtrueまたはfalseの値のみを返します。サブセットに含まれる要素（合計するとターゲットに等しくなるセット）も取得するにはどうすればよいですか？

動的計画法を使用する必要がありますか？私が知っているように、Coz ..再帰は実際にスタックを構築しており、関数が値を返した後、フレーム内の値も破棄されます。

それで、合計が目標値に等しい要素を取得することは可能ですか？

オブジェクトを渡すことは問題の解決策ですか？

ありがとうございました

4

1 に答える 1

5

まず最初に、プログラムを少し最適化することができます-ターゲットが0であるかどうか、そしてそれが常に返されるかどうかを確認してくださいtrue。ここで必要なのは、すでに使用した要素を保存する場所を用意することです。グローバルな「スタック」を使用してこれを行う方法を示します（vector実際には、スタックを反復処理できるようにするため）。コードが理解しやすくなりますが、関数を参照して渡すか、回避することもできます。他の方法でグローバルにします。ちなみに、stlコンテナはではsetなく呼ばれていSetます。

vector<int> used;
bool subsetSumExists(Set<int> & set, int target) {
    if (target == 0) {
        cout << "One possible sum is:\n";
        for (int i = 0; i < used.size(); ++i) {
          cout << used[i] << endl;
        }
        return true;
    } else if(set.empty()) {
      return false;
    }else {
        int element = set.first();
        Set<int> rest = set - element;
        used.push_back(element);
        if (subsetSumExists(rest, target- element)) {
          return true;
        } else {
          used.pop_back();
        }
        return subsetSumExists(rest, target);
    }
}

お役に立てれば。

于 2012-04-06T06:16:11.333 に答える