Imagine you are in charge of a cargo ship:
- travelling along a fixed route or loop (A, B, C, D, A...)
- has a maximum cargo capacity
At each stop you can:
- buy commodities, up to your cargo capacity, or sell cargo that you have already bought
- each stop has different prices for each commodity
- for simplicity, you can't run out of money for buying
- also for simplicity, cargo amounts are infinitely divisible, so there's no knapsack-problem-like issues
What algorithm can I use to determine the best commodities and amount to buy/sell at each stop, to make the most profit?
The solution is not just to buy low and sell high because you have limited cargo space, and there's a tradeoff between carrying profitable cargo between many stops and doing more trades at each stop. For example: given a route A -> B -> C, two commodities (apples, oranges) and the following prices:
Stop | Apples | Oranges -----+--------+-------- A | $1 | $1 B | $2 | $1 C | $4 | $3
The best action would be to buy apples at A and sell them at C, for a profit of $3 * capacity. But if oranges were to appreciate to $3 at B, then it would be better to buy oranges at A, sell them at B and buy apples, and sell the apples at C, for a total profit of ($2 + $2) * capacity.