math - 最小公倍数の合計と 2 組の数値の組み合わせの取得

Question

私は現在、C# でプログラムを作成しています。このプログラムは、2 つの数値セットの最小の等しい合計を探します。このプログラムでは、数値を何度でも繰り返すことができます。

たとえば、私はこれらの 2 つのセット{ 10, 13, 18 }とを持ってい{ 12, 16, 22 }ます。私が得ることができる最小の合計は28です:(10 + 18)そして(12 + 16).

別の例は{5, 7, 9}と{1, 2, 3}です。可能な最小の合計は5です(5)。and (1+1+1+1+1)or or (1+2+2)or(2+3)など。

どこから始めればよいか、何か提案はありますか? 私は実際にはセットごとに 6 つの数字を使用し、数字は数百 / 数千のマークにあります。

Answer 1

2つのセットを維持し、入力セットから初期化し、番号を増やして並べ替えます（たとえば、ツリーベースのセット構造を使用します）。次に、2つのセットの最初の（つまり最小の）要素を比較します。セットから削除した小さい方の要素を、対応する入力セットのすべての要素をその値に追加し、結果を挿入します。両方のセットに同じ最小要素がある場合、これで完了です。その要素は、最も一般的でない等しい合計です。