次の問題に対する最適なアルゴリズムの解決策を見つけようとしています。これは現実世界の問題ですが、抽象的な方法で提示します。
1000人のコミュニティがあります。各ユーザーには、設定された数のチケットが提供されます。チケットは4種類あります（それぞれ別のイベントに対応しています）。ただし、一部の人々は喜んで取引を行います (たとえば、私は 1 枚の A チケットが必要で、2 枚の B チケットを喜んで放棄します)。さらに、余分なチケットを持っている人もいますが、それを無料で配布します (たとえば、2 枚の C チケットを必要な人に配布します)。各人が何を喜んで譲渡/交換するかを知っていると仮定すると、どうすれば最も多くの人を満足させることができますか?
私はグーグルを試しましたが、金融商品のアルゴリズム取引に関連する結果を得ることを避けるために、この問題をどのように表現すればよいかわかりません。
ありがとう。
複数の次元があることを考えると、NP完全問題である可能性があります。多次元ナップサック問題と類似しています。
したがって、バックトラックアプローチを試すことをお勧めします。
貿易に関わっているすべての人から始めましょう。
最も赤字の原因となっている人を降順に並べ替えます（ここでは、各チケットタイプによって引き起こされた赤字を、各チケットの不足分で重み付けできます）。
次に、後戻りして、次に高い赤字の人を取引から追い出します。
チケットに不足がなくなるまで（可能な限り回答を記録する）、または全員を追い出すまで繰り返します。
それが起こったら、1ステップ戻って続行します（すでに最大の赤字を蹴ろうとした場合は、次に高い赤字の原因となる人を蹴ります）。
最後まで繰り返すか、時間がなくなるまで繰り返します。あなたが見つけた可能な答えから最適な答えを取得します。
問題が難しすぎる場合は、おそらく時間が不足します。そうでなければ、このアルゴリズムはあなたに合理的な答えを与えるはずです（おそらく最適に近い）。
この方法がどれだけうまく機能するかは、人々がどれだけ寛大で貪欲であるか、何人の人々がいるか、そしてあなたのコンピュータがどれくらい速いかによって異なります。
二部最小重みマッチング問題を探します。アイデアは、頂点 1 .. k のみを使用して i から j までの最短距離を見つけることです。