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. exist $ n $ different types of droids and $ k $ different planets Every planet $ p $ It has the following properties: there are $ s (j, p) geq 0 $ type droids $ j $ available for sale, at a fixed price of $ x (j, p) geq 0 $ each one for $ j = 1, 2, points, n $, and there is a demand for $ d (j, p) geq 0 $ type droids $ j $, at a fixed price of $ y (j, p) geq 0 $ every. (We will assume that a planet does not simultaneously have a

positive supply and a positive demand for a single type of droid; then for

every $ j $at least one of $ s (j, p) $ or $ d (j, p) $ is equal to $ 0 $.)

The player starts on the planet. $ s $ with $ z $ units of money and must finish

in the planet $ t $; there is a directed acyclic graph $ G $ in the set of planets, like

that s-t roads in $ G $ correspond to routes valid by the player. (G is chosen

be acyclic to avoid arbitrarily long games.) For a given s-t path $ P $ in

$ G $, the player can make transactions as follows. Whenever the player

reach a planet $ p $ in the path $ P $, she can buy up $ s (j, p) $ type droids $ j $ for $ x (j, p) $ units of money each (as long as you have enough money in

hand) and / or sell up $ d (j, p) $ type droids $ j $ for $ y (j, p) $ units of money (so I guess you can make multiple purchases / sales on each planet). The final score of the player is the total amount of money he has on hand when he reaches the planet. $ t $.

I am trying to prove that this problem is more difficult than some complete NP problem, but I am quite trapped. 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 on each planet. Also, this problem is a maximization problem, and I don't know many problems of full NP maximization other than quadratic allocation.

**Can I get a clue on how to do this? For example, what problem should X choose to reduce to the Droid Trader problem?** Thank you!