まず、問題に関するいくつかのコンテキスト:
いくつかのタイプのリソース (A、B、C...) を持つシステムで作業しています。いくつかのリソース要件が与えられており、それらを購入できるかどうかを判断する必要があります。
このために、いくつかのソースがあり、それぞれが複数のタイプのリソースを提供できますが、各リソースに使用するソースを選択する必要があります。
たとえば、1A、2B、および 0C ((1,2,0) として表される) を支払う必要があり、次のソースがあるとします。
- (1,1,0) //生産物 A または B を選択する必要があることを意味します
- (0,1,1) //生産物 B または C を選択する必要があることを意味します
- (1,1,0)
リソース B にソース 2 を使用しなければならないことは明らかであり、1 と 3 のどちらが A と B を生成するかを選択できます。
これを実装するための私のアプローチは、上記の状況が次のように表される依存グラフとして表示することです。
したがって、リソースをループし、すべてのリソースについて、それに到達するリンクをループします。現在のリソースの現在のノードを削除すると、残りの支払いコストを支払うのに十分な到達リンクが他のリソースに残っていることを意味する場合は、それを使用します。
前の例では、最初にリソース A にソース 1 を使用しようとします。B にはまだ 2 つのリンクがあるので、使用できます。タイプ B のリソースだけが残っているので、残りのリソースを使用して B を支払います。
これで問題ありませんが、新しいシナリオで作業する必要があります。ここでは、2 種類のソースがあり、それぞれが 1 種類のリソースをコスト 1 またはコスト 2 で生成し、総コストを最小限に抑える必要があります。
この例をわずかに変更すると、次のようになります。
常識的な解決策は、1 と 2 を使用して B に支払い、3 を使用して A に支払い、合計コスト 1 にする必要がありますが、上記のように、私の実装では、B にはまだ 2 つのリンクがあるため、ソース 1 を使用して A に支払います。そのため、最後にソース 3 をコスト 2 で使用する必要があります。
すべての選択肢の組み合わせを試すことを意味する解決策は、可能であれば避けるべきです。
このケースに適用できる既知の解決策を持つ一般的なアルゴリズムの問題について知っていますか? または、この新しいシナリオで機能するように実際のソリューションを改善するにはどうすればよいですか? それとも、別の別のアプローチを取る必要がありますか?
