通过交易最大化利润
maximize profit through trading
我在这个问题上卡了一段时间，想弄清楚下面这个问题的递归关系
问题描述：
假设市场中可能存在以下交易选项：
- 1 金属比 2 木材
- 1 木材比 0.2 玻璃
- 1 玻璃比 1.5 金属
- 1 木比 0.4 火
- 1火3金
确定是否有可能仅通过交易从某个项目上获利。
例如在上述场景中，我们可以通过执行以下操作在金属上获利：
1 金属 -> 2 木材 -> 0.8 火 -> 2.4 金属
我卡住的部分是如何分解子问题。这个问题似乎与括号乘法问题很相似，我们试图通过一系列乘法来最大化最终结果，但有更多限制。
我不想要完整的答案，但非常感谢能够将我推向正确方向的提示！
谢谢！
提示：您可以通过 "playing" 使用权重并将其简化为已知的加权最短路径问题来解决此问题。
剧透：详细解释
这可以通过在图上找到负权重循环很好地解决，权重为：
令w'(u,v)为将一单位u转化为v的成本。
定义：
w(u,v) = -log(w'(u,v))
想法是一条路径 v1->v2->...->vk 的成本为
COST = w(v1,v2) + w(v2,v3) + ... + w(vk-1,vk) =
= -log(w'(v1,v2)) + -log(w'(v2,v3)) + ... + -log(w'(vk-1,vk)) =
= -log (w'(v1,v2)*w'(v2,v3)*...*w'(vk-1,vk))
现在，很容易看出w'(v1,v2)*w'(v2,v3)*...*w'(vk-1,vk)的值恰好是一单位v1所产生的vk的数量。
类似地，对于从某个u到它自身的任何循环：u->v1->v2->v3->...vk->v，w'(u,v1)*w'(v1,v2),...,w'(vk,u)的值就是你可以这样生产多少单位，这个值大于1 当且仅当 -log(w'(u,v1)*w'(v1,v2),...,w'(vk,u) < 0
所以，这个问题可以很容易地简化为一个已知的算法 - Bellman-Ford，它可以很容易地检测负循环的存在。
我在这个问题上卡了一段时间，想弄清楚下面这个问题的递归关系
问题描述：
假设市场中可能存在以下交易选项：
- 1 金属比 2 木材
- 1 木材比 0.2 玻璃
- 1 玻璃比 1.5 金属
- 1 木比 0.4 火
- 1火3金
确定是否有可能仅通过交易从某个项目上获利。
例如在上述场景中，我们可以通过执行以下操作在金属上获利：
1 金属 -> 2 木材 -> 0.8 火 -> 2.4 金属
我卡住的部分是如何分解子问题。这个问题似乎与括号乘法问题很相似，我们试图通过一系列乘法来最大化最终结果，但有更多限制。
我不想要完整的答案，但非常感谢能够将我推向正确方向的提示！
谢谢！
提示：您可以通过 "playing" 使用权重并将其简化为已知的加权最短路径问题来解决此问题。
剧透：详细解释
这可以通过在图上找到负权重循环很好地解决，权重为：
令w'(u,v)为将一单位u转化为v的成本。
定义：
w(u,v) = -log(w'(u,v))
想法是一条路径 v1->v2->...->vk 的成本为
COST = w(v1,v2) + w(v2,v3) + ... + w(vk-1,vk) =
= -log(w'(v1,v2)) + -log(w'(v2,v3)) + ... + -log(w'(vk-1,vk)) =
= -log (w'(v1,v2)*w'(v2,v3)*...*w'(vk-1,vk))
现在，很容易看出w'(v1,v2)*w'(v2,v3)*...*w'(vk-1,vk)的值恰好是一单位v1所产生的vk的数量。
类似地，对于从某个u到它自身的任何循环：u->v1->v2->v3->...vk->v，w'(u,v1)*w'(v1,v2),...,w'(vk,u)的值就是你可以这样生产多少单位，这个值大于1 当且仅当 -log(w'(u,v1)*w'(v1,v2),...,w'(vk,u) < 0
所以，这个问题可以很容易地简化为一个已知的算法 - Bellman-Ford，它可以很容易地检测负循环的存在。