I have a game in which the goal is to craft objects and I need to formulate an optimization problem, but I don't know where to start.
Rules
In this game you have a backpack B where all your objects are stored. An object can be either craftable or base (not craftable).
Every craftable object must be crafted using the base item or other craftables objects, for example:
If I want to craft the object O which depends on base items $x_1,x_2,x_3$ and craftable items $y_1,y_2$, I need all of them to create the object O. Since the items $y_1,y_2$ are craftables themselves, they depend on other base items such as $x_4,x_5,x_6$. So in the end, to craft the object O i need $x_1,x_2,x_3,x_4,x_5,x_6$ base objects.
Every craftable object gives you some craft_points [CP] which includes all the chain of crafted object that you need to do it. More precisely, if I want to create the object O which will give me 200CP, the number of CP is the sum of the CPs for every object down the craft line.
For example the craftable object [$y_1,y_4,y_7$] give respectively [20,40,70]CPs. To craft the object O I need $y_1,y_4,y_7,x_3,x_2$ so that I will gain a total of 130CPs.
Data
I have access to a gamer backpack B, containing all his/her base/craftable objects, and i have a list of every possible item in the game, both base and craftables. For the craftable ones I have a list of base items that will be needed to craft the object, called dependencies.
Goal
My goal is to suggest to the gamer the most proficient items to craft, in terms of CPs, while assuring the following conditions:
- To craft an item the player must have all the dependencies base object in his backpack
- An item $O_1$ with 100CPs which needs a total of 30 base items to be crafted, is considered better than an item $O_2$ with the same amount of CPs that needs 31 base items to be crafted.
- Keep the variety of needed items large, i.e. do not use only a few base items for the craft.
So in the end this is a constrained maximization problem, but I don't know where to start for its formulation. I appreciate all the help you can give me.
This feels to me like one of the NP-hard problems. It is similar to the knapsack problem. There will be cases where it is very hard, where you have to try many of the possibilities, but in practice those seem to be rare. With reasonable numbers of objects it is often obvious what the right answer is. Your bullets at the end are a good start. Often there will be a few base items that are needed for many craftables and a number of base items that are only used occasionally. You should focus on the most popular ones, finding the highest value you can achieve from each one. Any craftable that uses more than one popular item better be very valuable to make up for it. You might be able to assign a price to each base item and find the best ratio of $CP/cost$ You might also have multiple copies of some base items, maybe even so many you can't use them all. These base items can be considered free.