制限付き入力と出力可能な出力を一致させるアルゴリズムはありますか？

Question

私は、ユーザーがさまざまな最終製品に変換できる入力製品のリストを提供するという問題に取り組んでいます。各入力プロダクトには、出力可能な特定の出力セットがあります。また、ユーザーは、期待される出力製品のリストと、それぞれがどれだけ必要な出力製品を提供します。私は可能な限り最高のフィット感で需要を満たすために様々な入力を出力に合わせるための既知のアルゴリズムがあるかどうかを調べることを検討しています。

例：Aは、製品XになることができるとY
製品Bは製品YとZ

になることができます

製品5 Aと7 B.
がありますが、あなたは3 Xを作ることができ、 4 Y、6 Z？

私は私が出力を見つけるのに役立つだろうなアプローチをしたいと思います：

3 A - > X
2 A - > Y
2 B - > Y
5 B - > Z
あなたのように構築フローネットワークにmax flow algorithmsのいずれかを適用することによって、この問題を解決することができZ

Answer 1

1欠落、以下：

• とSからエッジを追加するノードを追加し、各出力製品のI
• _{各入力製品のノードZ J}
• を追加各入力製品のソースノードSとシンクノードT
• を追加対応する製品の数に等しい容量
• 各出力製品について、対応する製品の所望の数に等しい容量でTにエッジを追加する
• 各Aから _iおよびZ _Jは_私製品ここで

ネットワークはあなたの例のためにどのように見えるかあるの数に等しい容量のエッジを追加します。

最大流量がTに入る総容量に等しい場合には、溶液を分猫によって定義されます。さもなければ、解決策は不可能です。

注：あなたが必要とするすべては、はい/いいえ答えがない場合は、_私ノードを排除することができる、とすべての上に、この出力の合計に等しい容量で、Z _JにSからエッジを追加（すなわち、X = 5、Y = 12、およびZ = 7）。これは同じ決定結果を生成しますが、プロセスで消費される必要がある各種類の入力プロダクトの数を確認することはできません。