I've got an idea for a tool I want to make but I am not sure how to go on about trying to solve it... I was hoping if you could help me classify it and also give me some suggestions on how I could try solving it.
This summer I played through the Persona 4 JRPG game, similar to Pokemon. In the game, you can collect and level up "personas". The game also features a system that allows players to combine personas through "fusion" to create other personas.
There are tools out there that calculate the various combinations of "parents" possible to create a certain persona. However, these tools only give the immediate parents, I want to create a tool that given a set of personas the player has available, shows all the fusions that need to be made to crate a persona, as cheaply as possible (there is a price involved).
There are about 100 or so personas in the game and each persona belongs to a certain arcana (type).
When a player has found a certain persona, he or she can "summon" (create) it later for a certain price. These summoning costs are what makes out the price for the total creation chain.
The fusion is done by combining two or three personas. The resulting persona's arcane is a look-up depending on the parents', and the resulting persona is then the persona with lowest rank in the given arcana with a rank greater than the average of the parents.
After fusion is done, the resulting persona is added to the list of available personas which the player can create.
Details of the fusion are explained in this link: http://persona4.wikidot.com/fusiontutor
Given a list of available personas, I want to return the whole "fusion-chain" while minimizing the total cost.
What makes this problem so difficult is the fact that the available personas changes depending on the order they are created. In general, it seems that it is cheaper to summon a persona than to summon its parents and fuse them. Because of this, it seems I would have to investigate every permutation possible...
I would like to classify this problem, is it np-complete? np-hard? or even worse? It looks like a simple dynamic programming problem, but what do you do when the result is dependent on the order in which you solve each sub-problem?
Also, I wonder if anyone has some ideas on how this could be solved, preferably with as low total cost as possible.
Note: I don't know about suitable tags so I would welcome suggestions for that as well :)