最佳配方顺序

Question

我假设下面的是/简化为一个已知的问题，但我一直未能找到它。

我有一系列的食谱和相关的费用。每个配方将一组资源转换为另一组资源。

也就是说。

• () -> (1A)费用1
• (2A) -> (1B，1C)费用2
• (4A) -> (3B，1C)费用2
• (1A，1B) -> (1C)成本1

现在，我希望找到一个资源(例如"C")的最大收益除以成本的步骤序列(或者仅仅是以某种有限的成本最大化资源收益的顺序)。

这个问题有名字吗?有没有比蛮力搜索更好的方法(也许有一些回忆录)？

Answer 1

这个问题可以在有向图中建模为最长路径搜索。图的每个顶点对应于一组当前可用的资源(从空集开始)，菜谱定义了从一组资源到一组新资源的可能边缘。作为边缘的权重，人们应该选择任何一个

• "# C“本身的增加
• "#当前C/除以当前总成本“-”应用该配方后的C#/除以该配方后的总成本“

取决于问题的两个变体中的哪一个想要解决。

对于给定的问题陈述，图在理论上是无限的，但通过增加一些合理的限制，如最大的代价，或者要应用的步骤/配方的最大数目，就可以使它变得有限。

如果菜谱构造合理，它们将保证图形保持无循环，在这种情况下，正如维基百科所述，可以使用最短路径搜索的技术来解决问题。但要小心，如果有食谱允许中间消耗的“目标资源”，导致负权重。如果有可能让图包含循环的菜谱，这可能会成为NP难题。

Answer 2

这个问题可以建模为覆盖问题 (来源)的一个实例。

将资源0编号为m-1，将菜谱编号为0到n-1。

现在设A_i，j是从配方j到资源i的变化，a现在是维数m的矩阵，c_j是执行食谱J的成本，c是维数n的向量。

我们现在可以提出这个问题:最小化实现资源I的b_i项的成本(不是我要求的问题，而是足够接近的问题)。B是维数m的向量。

设x_j是我们使用食谱j的次数，x是维数n的向量。

我们希望在Ax>=b和x>=0约束下最小化c^ to。

这是一个覆盖问题，它有多个线性优化解。

该算法忽略了解决方案可能是非整数的(我们只需缩放解决方案以获得整数解:如果输入是有理的，则应该是合理的)，并且解决方案在某些资源中可能暂时下降到零以下(假设我们开始时有足够的资源来处理资源的临时下降)。