3

これはstackoverflowの私の最初の投稿です。

金融アプリケーションのアルゴリズムをアドバイスする必要があります。このような数字のリストが2つあると仮定します（はい、それらは銀行取引です）：

List 1          | List 2
-------------------------------------
1000            | 200
7000            | 300
3000            | 10000
16000           | 500
                | 16000
                | 4100

いくつかの条件を考慮して、数字を互いに一致させる必要があります。

  1. 一致は、1対1、1対多、または多対多の場合もあります。したがって、ここでは2つの16000一致（1対1）、リスト1の1000はリスト2の200 + 300 + 500（1対3）、リスト2の10000はリスト1の7000 + 3000（1対3）と一致します。 to-two）など。

  2. フィギュアは複数の試合で使用できます。

  3. 2つのリストの数字の数は、等しい場合と等しくない場合があります。

  4. 1対多の試合での最大数字数は設定可能である必要があります。

  5. 多対多の試合は必須ではありません。しかし、私たちもそれらを持っているといいでしょう！

  6. 一部の数字は比類のないままになっている可能性があります。大丈夫です。

これを実現するために私が行っているのは、2つの複雑なネストされたループを使用することです。動作しますが、フィギュアの数、または各試合で許可されるフィギュアの最大数が増えるにつれて、完了するまでに時間がかかります！

これを行うためのより良いアルゴリズムはありますか？

4

2 に答える 2

3

私は断言するのが正しいと思います。私が間違っている場合、SOは私にキックを与えます。つまり、計算のカーネルはNP困難です。つまり、多項式時間の解を見つける可能性は非常に低いということです。 。カーネルには、単一の番号（など）と他の番号のリストが与えられ、合計が単一の番号になるリストのすべてのサブセットが検索されます。10000

このカーネルは、部分和問題のバリエーションです。

それを考えると、あなたが見つけることができるアルゴリズムがどれだけ優れているかには限界があり、「速い」アルゴリズムを見つけるというあなたの期待は失望する可能性があります。

アルゴリズムを高速化するには、両方のリストを並べ替えることから始めることをお勧めします。リスト1から最初の番号を取得し、リスト2から、リスト1の番号以下のすべての番号を取得し、一致するものを見つけて、繰り返します...次に、リスト2の番号を番号ごとに調べます...

于 2013-02-14T13:33:13.753 に答える
0

これを行うには、まず各リストの組み合わせを生成します。たとえば、リスト 1 の組み合わせは次のとおりです。

1000
3000
7000
16000
1000 3000
1000 7000
1000 16000
3000 7000
3000 16000
7000
1000 3000 7000
1000 3000 16000
1000 7000 16000
3000 7000 16000
1000 3000 7000 16000

組み合わせごとに、組み合わせ内のアイテムの合計を生成します。これで合計の 2 つのリストができました。この問題を解決するには、2 つのリストを交差させます。交差を実行するためのさまざまなアルゴリズムがあります。簡単な方法の 1 つは、2 つのリストのうち小さい方をバイナリ ツリーにすることです。次に、より大きなリストの各項目について、バイナリ ツリーで見つけます。このアルゴリズムの複雑さは n*log(n) 時間です。

于 2013-02-14T16:16:56.047 に答える