This question is from Algorithms Design.
A player in the game controls a spaceship and is trying to make money buying and selling droids on different planets. There are $ n$ different types of droids and $ k$ different planets. Each planet $ p$ has the following properties: there are $ s(j, p) \geq 0$ droids of type $ j$ available for sale, at a fixed price of $ x(j, p) \geq 0$ each, for $ j = 1, 2, \dots , n$ , and there is a demand for $ d(j, p) \geq 0$ droids of type $ j$ , at a fixed price of $ y(j, p) \geq 0$ each. (We will assume that a planet does not simultaneously have both a positive supply and a positive demand for a single type of droid; so for each $ j$ , at least one of $ s(j, p)$ or $ d(j, p)$ is equal to $ 0$ .)
The player begins on planet $ s$ with $ z$ units of money and must end at planet $ t$ ; there is a directed acyclic graph $ G$ on the set of planets, such that s-t paths in $ G$ correspond to valid routes by the player. (G is chosen to be acyclic to prevent arbitrarily long games.) For a given s-t path $ P$ in $ G$ , the player can engage in transactions as follows. Whenever the player arrives at a planet $ p$ on the path $ P$ , she can buy up to $ s(j, p)$ droids of type $ j$ for $ x(j, p)$ units of money each (provided she has sufficient money on hand) and/or sell up to $ d(j, p)$ droids of type $ j$ for $ y(j, p)$ units of money (so I’m assuming you can make multiple buy/sells at each planet). The player’s final score is the total amount of money she has on hand when she arrives at planet $ t$ .
I’m trying to prove this problem is harder than some NP-complete problem, but I am quite stuck. Since the planets are organized in a DAG, I think the ‘hardness’ of the problem comes from the fact that you can buy and sell many different types of droids at each planet. Also, this problem is a maximation problem, and I don’t know many NP-complete maximization problems other than quadratic assignment.
Can I get a hint on how to do this? Such as what problem X should I choose to reduce to Droid Trader Problem. Thanks!