-6

各数量を整数に分割し、同じ比率を使用する必要があるように、設定された数の受信者間で分割する必要がある複数 (数千) の数量があるという問題があります。これを確実かつ効率的に実装するアルゴリズムを見つける必要があります (私たち全員ではありませんか?:-) )

これは、注文が何千もの「約定」を得る可能性があり、注文の平均価格を維持しながら、一日の終わりに少数のクライアントに分配しなければならない金融市場 (証券取引所注文) の問題を解決するためです。次に例を示します。

合計注文数量 37300

証券取引所が記入した数量

約定 1. 16700 株が価格 75.84 で約定

約定 2. 価格 75.85 で約定した 5400 株

約定 3. 価格 75.86 で約定した 4900 株

約定 4. 価格 75.87 で約定した 10300 株

平均価格で約定した 37300 株 = (16700*75.84 + 5400*75.85 + 4900*75.86 + 10300*75.87) / 37300 = 75.85235925

これらの数量を次のように 3 つのクライアントに分割する必要があるとします。

Client1: 15000 株

Client2: 10000 株

Client3: 12300 株

各実行は個別に分割する必要があります (各クライアントが要求した数量を平均価格で価格設定することはできません)

私の最初の考えは、それぞれを比例して分割することでした:

クライアント 1 は 15000/37300=0.402144772 を取得します

クライアント 2 は 10000/37300=0.268096515 を取得します

クライアント 3 は 12300/37300=0.329758713 を取得します

それはにつながるだろう

Client1 - 15000 Client2 - 10000 Client3 - 12300 比率: 0.402144772 比率: 0.268096515 比率: 0.329758713

分割 (フォーマットについては申し訳ありません - これが投稿エディターでできる最善の方法でした)

+-------------+-------------+-------------+
| Client 1    | Client 2    | Client 3    | 
+-------------+-------------+-------------+ 
| 6715.817694 | 4477.211796 | 5506.970509 | 
| 2171.581769 | 1447.72118  | 1780.697051 |
| 1970.509383 | 1313.672922 | 1615.817694 |
| 4142.091153 | 2761.394102 | 3396.514745 |
+-------------+-------------+-------------+
| Totals:     |             |             |
|       15000 |       10000 |       12300 | 
+-------------+-------------+-------------+

これに関する問題は、クライアントに端数を割り当てることができないため、これらの分割の端数部分が 0 になるように数量を調整するスマートなアルゴリズムが必要であることです。これは多くのシナリオでは不可能であることを理解しているため、この要件は特定のクライアントがもう少し多く (または少なく) 取得できるように、少しリラックスしてください。

この問題の出発点として使用できるアルゴリズムを知っている人はいますか?

4

2 に答える 2

1

最後の数値 (おそらく最小) を除くすべての数値 (ratio[n] * totalQuantity) を四捨五入できます。最後の数値は、totalQuantity (他の数値の合計) でなければなりません。これにより、選択した比率に近い正しい合計を取得しながら、整数の数量が得られます。

于 2012-09-17T16:25:36.047 に答える
0

これを別の角度から見てみてください。各クライアントが取得しているシェアの数はすでにわかっています。それぞれが支払わなければならない公正な合計金額を計算し、丸め誤差なしでこれを行う必要があります。

したがって、この合計金額に四捨五入の問題がない、つまり 0.01 の精度が必要です。

次に、金額を使用して価格を計算し、必要な精度で表示できます。

反対に (価格を計算してから金額を導出する) と、ドル金額の丸めの問題が常に生じます。

価格が 100 ユニットあたりであると仮定すると、これを達成する 1 つの方法は次のとおりです。

  1. 注文の合計金額を計算します (16,700*75.84/100 + 5,400*75.85/100 + 4,900*75.86/100 + 10,300*75.87/100) = $28,292.93

  2. 注文数量/満たされた数量の比率に基づいて、1 を除くすべてのクライアントを割り当てます。

クライアント 2 = $28,292.93 / 37,300 * 10,000 = $7,585,24 価格 = 7,585,24 / 10,000 * 100 = 75.8524.

クライアント 3 = $28,292.93 / 37,300 * 12,300 = $9,329.84 価格 = $9,329.84 / 12,300 * 100 = 75.85235772

  1. 最後のクライアントを残りの $$$ として計算します。

$28,292.93 - ($7,585,24 + $9,329.84) = $11,377.85. 価格 = $11,377.85 / 15,000 * 100 = 75.85233333

ここでは任意に、残数計算の対象となる数量が最も多いクライアント 1 を選択しました。

于 2012-09-17T16:39:07.887 に答える