10

最近、インタビューで次のような質問を受けました。たとえば、A = [3, 5, 9] と B = [7, 5, 1] のように、同じ長さ N の数のセットが 2 つあります。次に、範囲 0..N-1 の各位置 i に対して、数値 A[i] または B[i] のいずれかを選択できるため、最後に、A と A の要素で構成される長さ N の別の配列 C が得られます。 B. C のすべての要素の合計が K 以下の場合、そのような配列は適切です。配列 A、B、および数 K を指定して、適切な配列の総数を計算するアルゴリズムを作成してください。

私が思いついた唯一の解決策は、動的計画法のアプローチです。サイズが NxK の行列があり、M[i][j] は、現在の合計が j に等しい場合、数値 X[i] に対していくつの組み合わせを使用できるかを表します。しかし、彼らは私が公式を考え出すことを期待していたようです. それを手伝ってくれませんか？せめてどの方向を探せばいいの？どんな助けにも感謝します。ありがとう。

4

4 に答える 4

9

いくつか検討した結果、これは NP 完全問題であると思います。検討：

A = [0, 0, 0, ..., 0]
B = [b1, b2, b3, ..., bn]

3 番目のセットのすべての構成は、 のサブセットと のC = ( A[i] or B[i] for i = 0..n )サブセットの和集合であることに注意してください。この場合、 のすべての部分集合は に合計されるため、 の合計は の一部の部分集合の合計と同じになります。ABA0CB

Cさて、あなたの質問は、「以下の合計でいくつの方法を構築できますKか?」という質問です。B「以下の合計の部分集合はいくつありKますか?」と言い換えることができます。この問題をK = 1と で解くと、 の部分集合和問題のK = 0解が得られます(2 つの解の差は、合計が 0 になる部分集合の数です)。B

同様の議論により、Aゼロ以外の要素を含む一般的なケースでも、配列 を構築できS = [b1-a1, b2-a2, b3-a3, ..., bn-an]、問題は「和の部分集合がS未満になるのはいくつあるのK - sum(A)か?」となります。

部分和問題は NP 完全なので、この問題も NP 完全でなければなりません。そのことを念頭に置いて、あなたが提案した動的プログラミング ソリューションがあなたができる最善の方法であり、魔法の公式など存在しないことは確かです。

于 2012-10-03T01:28:43.247 に答える
0

これは私が問題を解決しようとする方法です（その愚かな場合は申し訳ありません）

配列について考える

A=[3,5,9,8,2]
B=[7,5,1,8,2]

要素0..N-1の場合

選択肢の数

2 ^ N

C1=0,C2=0

for all A[i]=B[i] 
{
    C1++
    C2+=A[i]+B[i]
}

次に、次のような新しい2つのアレイを作成します

A1=[3,5,9]
B1=[7,5,1]

また今C2は10です

これで、すべての選択肢の数が2 ^（N-C1）に減りました。

今、すべての良い数を計算します

K=K-C2として「K」を使用

残念ながら、どの方法を使用しても、合計2 ^（N-C1）回を計算する必要があります

于 2012-10-03T01:13:15.320 に答える
0

したがって、各ポイントで A または B から選択するため、2^N の選択肢があります。特定の例では、N がたまたま 3 である場合に 8 があります。議論のために、決定の各セットをビットパターンとして特徴付けることができます。

そのため、ブルート フォース アプローチではすべてのビット パターンを試します。

しかし、明らかなことは、最初の数ビットが生成する数値が大きすぎる場合、後続の可能性のあるテール ビットのすべてのグループも大きすぎる数値を生成するということです。したがって、おそらくそれをモデル化するためのより良い方法は、すでに限界を超えて成長している手足を歩くことを気にしない木です.

各ビットからテーブルの最後まで到達できる最大合計を計算することもできます。任意の時点で、現在の合計とこれから取得できる最大値が K 未満である場合、現在の場所からのすべてのサブツリーは、トラバーサルを必要とせずに受け入れられます。コメントで説明されているように、すべての組み合わせが許容されるケースは、この観察の特殊なケースです。

以下で Serge が指摘したように、関連する観察は、最小値を使用し、逆のロジックを使用して、トラバーサルなしでサブツリー全体をキャンセルすることです。

さらなる最適化の可能性は、加算が交換可能であるため、それぞれを同じようにシャッフルする限り、A と B の順序を変更しても効果がないという観察の背後にあります。したがって、最大値ができるだけ早く増加するか、最小値ができるだけゆっくりと増加するように努力して、トラバーサルから可能な限り早く終了するように努めることができます。実際には、絶対最大値と最小値 (いずれも計算済み) を K と比較するヒューリスティックを適用することをお勧めします。

その場合、再帰的な実装が最も簡単です。たとえば（Cで）

/* assume A, B and N are known globals */

unsigned int numberOfGoodArraysFromBit(
           unsigned int bit,
           unsigned int runningTotal,
           unsigned int limit)
{
    // have we ended up in an unacceptable subtree?
    if(runningTotal > limit) return 0;

    // have we reached the leaf node without at any
    // point finding this subtree to be unacceptable?
    if(bit >= N) return 1;

    // maybe every subtree is acceptable?
    if(runningTotal + MAXV[bit] <= limit)
    {
        return 1 << (N - bit);
    }

    // maybe no subtrees are acceptable?
    if(runningTotal + MINV[bit] > limit)
    {
        return 0;
    }

    // if we can't prima facie judge the subtreees,
    // we'll need specifically to evaluate them
    return
       numberOfGoodArraysFromBit(bit+1, runningTotal+A[bit], limit) +
       numberOfGoodArraysFromBit(bit+1, runningTotal+B[bit], limit);
}

// work out the minimum and maximum values at each position
for(int i = 0; i < N; i++)
{
    MAXV[i] = MAX(A[i], B[i]);
    MINV[i] = MIN(A[i], B[i]);
}

// hence work out the cumulative totals from right to left
for(int i = N-2; i >= 0; i--)
{
    MAXV[i] += MAXV[i+1];
    MINV[i] += MINV[i+1];
}

// to kick it off
printf("Total valid combinations is %u", numberOfGoodArraysFromBit(0, 0, K));

私は即興で考えているだけです。より良い解決策が存在する可能性があります。

于 2012-10-03T00:54:45.273 に答える
0

「指定された配列 A、B、および数 K から適切な配列の総数を計算するアルゴリズムを作成してください。」

それがゴールではないでしょうか。

int A[];
int B[];
int N;
int K;
int Solutions = 0;

void FindSolutons(int Depth, int theSumSoFar) {
    if (theSumSoFar > K) return;
    if (Depth >= N) {
    Solutions++;
    return;
    }

    FindSolutions(Depth+1,theSumSoFar+A[Depth]);
    FindSolutions(Depth+1,theSumSoFar+B[Depth]);
}

FindSolutions両方の引数をゼロに設定して呼び出します。返さSolutionsれると、 は適切な配列の数に等しくなります。

于 2012-10-03T00:55:11.370 に答える