通过交易最大化利润 [英] maximize profit through trading

问题描述

我一直在这个问题上停留一段时间，试图找出以下问题的重复关系。

问题描述：

假设在市场上可能有以下交易选择：

• 1种金属对2种木材


• 1木材至0.2玻璃


• 1玻璃至1.5金属


• 1木材至0.4火


• 1击中3种金属

确定是否有可能仅通过交易就在某个项目上获利。

例如，在上述情况下，我们可以通过以下操作在金属上获利：

1金属-> 2木材-> 0.8火-> 2.4金属

我遇到的问题是如何分解子问题。圆括号乘法问题似乎很熟悉这个问题，我们试图通过一系列乘法来最大化最终结果，但有更多限制。

我不希望完整的答案，但能使我朝正确的方向前进的提示将不胜感激！

谢谢！

解决方案

提示：您可以通过玩弄权重并将其减少为已知的加权最短路径问题来解决此问题。

---

剧透：详细说明

这可以通过在负数上找到负的权重循环来很好地解决。图，具有权重：

让 w'（u，v）是转换 u 转换为 v 。
定义为：

  w（u，v）= -log（w'（u，v））
  

这个想法是路径 v1-> v2-> ...- > vk 的成本为

 成本= 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）恰好是 vk 是从一个 v1 的单位产生的。





类似地，对于某些 u 本身： u-> v1-> v2-> v3-> ... vk-> v ， w'（u，v1）* w'（v1，v2），...，w'（vk，u）的值是您可以生产多少个单位这样，且仅当 -log（w'（u，v1）* w'（v1，v2），...，w'（vk，u）时，此值才大于1 < 0

因此，可以很容易地将此​​问题简化为已知算法-贝尔曼·福特，可以轻松检测到负循环的存在。 / p>

I have been stuck on this question for a while trying to figure out the recurrence relationship for the following problem.

Problem description:

Suppose in a market the following trade options are possible:

• 1 metal to 2 wood
• 1 wood to 0.2 glass
• 1 glass to 1.5 metal
• 1 wood to 0.4 fire
• 1 fire to 3 metal

Determine if it's possible to make profit on a certain item simply by trading.

For example in the described scenario above, we can make a profit on metal by doing the following:

1 metal -> 2 wood -> 0.8 fire -> 2.4 metal

The part where I'm stuck at is how the subproblems should be broken down. This problem seems familiar to the parenthesis multiplication problem, where we are trying to maximize the end result through a series of multiplications but with more restrictions.

I don't want the full answer but hints that can nudge me towards the right direction would be really appreciated!

Thanks!

解决方案

Hint: You can solve this problem by "playing" with the weights and reducing it to a known weighted shortest-path problem.

---

Spoiler: detailed explanation

This can be solved nicely by finding a negative wight cycle on a graph, with weights:

let w'(u,v) be the cost of transforming one unit of u into v. define:

w(u,v) = -log(w'(u,v))

The idea is a path v1->v2->...->vk has the cost of

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))

Now, it is easy to see that the value of w'(v1,v2)*w'(v2,v3)*...*w'(vk-1,vk) is exactly the amount of vk produced from one unit of v1.

Similarly, for any cycle from some u to itself: u->v1->v2->v3->...vk->v, the value of w'(u,v1)*w'(v1,v2),...,w'(vk,u) is how many units you can produce this way, and this value is bigger than 1 if and only if -log(w'(u,v1)*w'(v1,v2),...,w'(vk,u) < 0

So, this problem can be easily reduced to a known algorithm - Bellman-Ford, which can detect existence of negative cycles easily.

这篇关于通过交易最大化利润的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！