-4

サイズ n の整数の配列を、2 つ以上の数値を乗算するだけで 2 つの数値に削除したいと考えています。これらの 2 つの数値 (M1 と M2) の条件は、M1-M2 の減算の結果が他の可能なケースの中で小さい値になることです。次の例は、問題をより詳細に示しています。

配列のサイズが 4 で、要素が [n1,n2,n3,n4] であるとします。

可能な除去は次のとおりです。

M1 = n1 および M2 = n2xn3xn4

M1 = n2 およびM2 = n1xn3xn4

M1 = n3 およびM2 = n1xn2xn4

M1 = n4 およびM2 = n1xn2xn3

M1 = n1xn2 およびM2 = n3xn4

M1 = n1xn3 およびM2 = n2xn4

M1 = n1xn4 およびM2 = n2xn3

M1 = n2xn3 およびM2 = n1xn4

M1 = n2xn4 およびM2 = n1xn3

M1 = n3xn4 およびM2 = n1xn2

この例では、M1とM2の可能な値が 10 あります。私の問題で必要な正しい値は、他の 9 つの値の中で ABS( M1 - M2 ) の最小値です。複数の正解 (類似) になる可能性がありますが、これは無視できます。必要な出力は、M1に 1 つの値、M2に 1 つの値です。

注: C++ であればありがたいです :)

前もって感謝します...

4

1 に答える 1

1

std::next_permutation入力配列のすべての順列を生成するために使用することをお勧めします。順列ごとstd::accumulateに複数回使用して、異なる製品を作成します (つまりM1、順列の最初の要素だけでM2残りの製品が 1 つM1、最初の製品が 1 つの製品です)。順列の 2 つの要素とM2残りの要素など、真ん中に到達するまで続きます)。

ただし、これはいくつかの重複した積を生成するため、最適ではありません。つまり、 と で置換[n1, n2, n3, n4]を処理し、後で と で置換M1 = n1 * n2を処理します。この解法は非常に単純で書きやすいですが、乗算が可換であるという事実を利用できていません。M2 = n3 * n4[n2, n1, n4, 3]M1 = n2 * n1M2 = n4 * n3

于 2013-07-30T09:55:31.807 に答える