0

私の問題は説明するのが少し難しいので、最善を尽くします。ターゲット番号と他の番号のリストを受け取るプログラムを書いています。リストの合計からの数字の組み合わせがターゲット数と同じになるまで、リストからの数字のすべての可能な組み合わせを追加したいと思います。たとえば、ターゲット番号が 6 で、提供されたリストの番号が <2, 3, 4, 5> の場合、プログラムは解を 2+4=6 として出力します。

私は現在、最も外側のループが最初の数値との組み合わせを定数としてチェックする4つのネストされたループでプログラムをセットアップしています。2 番目のループは 2 番目の定数を保持し、他の 2 つについても同様です。上記のリストのターゲット数が 20 の場合、プログラムは次の方法でチェックします。

2
2+3
2+3+4
2+3+4+5
2+3+5
2+4
2+4+5
2+5
3
3+4
3+4+5
3+5
4
4+5
5

その後、解決策が見つからないというメッセージが返されます。これは小さなリストでは問題なく機能しますが、リストに多数の小さな数字が含まれていてターゲットの数字が大きい場合はうまく機能しません。このプログラムには 4 つのループしかないため、最大で 4 つの数値しか追加できません。

これを行うためのより良い方法があるに違いないと考えずにはいられません。長いリストの場合、唯一の解決策はネストされたループをさらに作成することであり、これは実用的ではありません。ネストされたループを使用せずに、数値のリストのすべての組み合わせを調べる方法はありますか?

これが理解しやすかったことを願っています。私のコードをご覧になりたい場合は、お知らせください。ご協力ありがとうございました！

4

3 に答える 3

0

次のような再帰的アプローチを使用できます。

#include <iostream>
#include <vector>

using namespace std;

vector<bool> active_pos;
vector<int> input;

int recurse (int current_sum, int target_sum, int length) {
    if (length < 0) {
        return -1;
    }

    for (int i = 0; i < input.size(); i++) {
        if (active_pos[i]) {
            continue;
        }

        active_pos[i] = true;

        int tmp_sum = current_sum + input[i];


        if (tmp_sum == target_sum) {
            return tmp_sum;
        }

        int next_sum = recurse(tmp_sum, target_sum, length-1);
        if (next_sum == target_sum) {
            return next_sum;
        }

        active_pos[i] = false;
    }
    return -1;
}

int main(int argc, const char **argv) {
    input.push_back(2);
    input.push_back(3);
    input.push_back(4);
    input.push_back(5);
    input.push_back(6);

    int length = input.size();
    active_pos.resize(length);

    int res = recurse(0, 10, length);

    cout << "Result is: " << res << endl;
    cout << "Used numbers are: " <<  endl;
    for (int j = 0; j < length; j++) {
        if (active_pos[j]) {
            cout << input[j] << " ";
        }
    }
    cout << endl;
}

関数はそれ自体を呼び出し、毎回パラメーターを 1 ずつrecurse()減らします。lengthベクトルは、既に取得された値を追跡します。

のインスタンスがrecurse()一致する合計を見つけた場合、その値を返します。そうでない場合は -1 を返します。最終結果が -1 の場合、一致は見つかりませんでした。

于 2013-11-10T12:03:48.927 に答える
0

私はこれに別の方向からアプローチします....リストのすべての数字を一緒に追加し、それが目標値と等しくない場合は完了です....リストの追加が目標よりも大きい場合、次に、目標値に一致するまで、リストの先頭からアイテムを削除し始めます。一致しない場合 (ターゲット値でスキップ)、加算値がターゲット値よりも小さくなった場合は、そのシナリオを適切に処理します。

これには 1 つのループのみが必要です。

于 2013-11-10T11:46:52.423 に答える
0

各組み合わせをN1 ビット値として表すことができ、その要素を組み合わせに含める必要がある場合に設定できます。次に、すべての組み合わせを反復することは、設定されたビットに対応する値を合計する内部ループを使用して、1 から 2 Nまでカウントすることと同じです。

セットのサイズが 64 以下の場合は、uint64_tループ カウンターを使用してこれを非常に簡単に行うことができます。それよりも大きい場合は、とにかく結果を見るのに十分な長さではないでしょう.

于 2013-11-10T13:42:13.210 に答える