maximize profit through trading

Question

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!

Answer 1

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.