algorithm - 是否有一种算法可以将受限输入与可能的输出相匹配？

Question

我正在解决一个问题，即用户提供可以转化为不同最终产品的输入产品列表。每个输入产品都有它可能成为的一组特定输出。用户还提供了预期输出产品的列表以及他们想要的每种产品的数量。我想看看是否有一种已知的算法可以将各种输入与输出相匹配，从而尽可能地满足需求。

示例:

Product A can become products X and Y
Product B can become products Y and Z

There are 5 A and 7 B.
Can you make 3 X, 4 Y, and 6 Z?

我想要一种可以帮助我找到输出的方法:

3 A -> X
2 A -> Y
2 B -> Y
5 B -> Z
缺少 1 个 Z

Answer 1

您可以通过应用 max flow algorithms 中的任何一个来解决这个问题。到如下构造的流网络:

• 添加源节点S和汇节点T
• 为每个输入产品添加节点 A_i
• 为每个输出产品添加节点 Z_j
• 对于每个输入产品，从 S 添加一条边，其容量等于相应产品的数量
• 对于每个输出产品，向 T 添加一条边，其容量等于相应产品的所需数量
• 从每个 A_i 和 Z_j 添加一条边，其容量等于 A_i 产品的数量

以下是网络如何查找您的示例。

如果最大流量等于进入T的总容量，则由min cat定义一个解；否则，解决方案是不可能的。

注意:如果您只需要一个是/否答案，您可以消除 A_i 节点，并添加从 S 到 Z_{j ，容量等于所有输入产品的此输出的总和(即 X=5、Y=12 和 Z=7)。这将产生相同的决策结果，但您将无法找出在此过程中需要消耗多少种投入品。}