0

この特定のケース（C＃またはelseアルゴリズム）のサブセット合計問題の解決策を探しています：

1) セットには約 1,000 の数字があります (数千になる可能性があります)。

2) 総額は数十億に達する

3) 数値は通貨値であるため、小数点以下 2 桁の精度を持ちます (例: 2,345.17)

4) セット内の数値は、正と負の両方になる可能性があります (したがって、正味合計を扱う)

次に、この検索を (同じ数のセットで) 繰り返す必要がありますが、合計は最大 1,000 回までです。そして最後に、プロセス全体が 1,000 回実行されます。つまり、1,000,000 回の実行を見ています。目標は、2分でそれを達成することです。つまり、各実行にかかる時間は 0.12 ミリ秒以内です。

これは実現可能ですか？

-クリップ

4

1 に答える 1

0

1,000要素に対してこれを行うためのリモートで（最適な答えのために）唯一の扱いやすい方法であるDP疑似ポリアルゴリズムについてすでに知っていると仮定します

アルゴリズムが通常実装される方法には、最大合計のサイズの配列が含まれ、それぞれがそのインデックスの数値の異なるバケットを表します。これを小数に適応させるには、データを小数から整数に変換する必要があります (100 を掛けて)。セットデータ構造を使用してこれを実装することもできます。これは、はるかに簡単でスペース効率が良い場合があります。

例えば、

import copy
j = {0:1}
lst = [1,2,8,2.3,214]

for i in lst:
    newj = copy.copy(j)
    for k in j:
        newj[k+i]=1
    j = newj

別の合計でサブセット合計アルゴリズムを繰り返しても問題にはなりません。DP アルゴリズムに従う場合は、すべての可能な合計を 1 回計算してから、毎回新しい合計についてセットを再確認できます。

本当の問題は、アルゴリズムが進むにつれてセットが大きくなるため、セットのサイズが大きくなることです。最悪の場合、セットのサイズは要素の数とともに指数関数的に増加します (すべての合計は一意であり、2^n 要素)。多少の重複があれば、より良いでしょう。私は1000要素を推測していますが、範囲が広いと問題が発生する可能性があります.

于 2011-07-08T17:18:28.760 に答える