各数量を整数に分割し、同じ比率を使用する必要があるように、設定された数の受信者間で分割する必要がある複数 (数千) の数量があるという問題があります。これを確実かつ効率的に実装するアルゴリズムを見つける必要があります (私たち全員ではありませんか?:-) )
これは、注文が何千もの「約定」を得る可能性があり、注文の平均価格を維持しながら、一日の終わりに少数のクライアントに分配しなければならない金融市場 (証券取引所注文) の問題を解決するためです。次に例を示します。
合計注文数量 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 になるように数量を調整するスマートなアルゴリズムが必要であることです。これは多くのシナリオでは不可能であることを理解しているため、この要件は特定のクライアントがもう少し多く (または少なく) 取得できるように、少しリラックスしてください。
この問題の出発点として使用できるアルゴリズムを知っている人はいますか?