The problem I am trying to solve is to find the fastest way to produce an total amount of something. There are several different producers that each have a different production and cost (based on the number of the item that is already owned) which can be purchased during production.For example, assume that the goal is to produce 1000 units total (including the amount spent on buying new producers), and the three producers that can be bought $A$, $B$, and $C$, have productions and base costs of $1$ per second and $20$, $7$ per second and $50$, and $14$ per second and $100$, respectively. Buying a producer multiples the price of the next producer of the same type by 1.1 (so, for example, buying an $A$ for the base price of 20 means the next $A$ will cost $1.1 \cdot 20 = 22$, and the next $1.1 \cdot 22 = 24.2$, et cetera). When a producer is bought, the price of the produced is subtracted from the current units produced, but not the total production (so if you have 30 units, and you buy an A, you now have 10 units left). Selling a producer returns half of the units used to purchase it, and reduces the cost by 1.1 times (so if the cost was at 24.2, it would go down to 22). By starting with 1 $A$, what is shortest amount of time to produce 1000 units and in what order should you purchase producers?The shortest time is 68 seconds, buying producers in the following order:A,B,B,B,C,C,C,C.My first solution was simply to try all the different sequences, then determine the one that will be the fastest after $n$ purchases, but, naturally, this was very slow.My second solution was to try a greedy search where I just look for the best solution in terms of time at every step.My third solution was to try a search where I used the increased in production as the score for each sequence, and backtrack to earlier solutions if any of them had better scores.Are there any other problems or generalizations I can make to find an optimal (or near optimal solution faster)?
How can I do an optimization problem that involves finding a sequence?
optimization