Algorithm for finding the optimal passage of the game level. Which one to use?

Question

Algorithms

I'm making a little game. Initially, to complete the level, it was required to score N number of points. I used the " finding change " algorithm (sorry, I don't know how it is in Russian): you find the minimum number of "coins" you need for change. In this case, some game items acted as coins. For example, to score 100 points and advance to a new level, you need to find 1 box of matches, which gives 75 points, and 1 axe, which gives 25 points. There are other elements on the level that give different points. The point is to make the level optimal in difficulty.
In the new iteration, we decided to give each game item, in addition to points, energy. It can be both negative and positive. For example, when you find matches, you get 75 points and 10 energy, and an ax gives 25 points and -10 energy.
To complete the level, the player must always be in the black in terms of energy. And this is where I'm a little stuck as to how do I calculate the optimal number of items to collect to advance to the next level.
Are there any already known algorithms that you can just take? Or should I somehow customize the existing one?

Answer 1

I found a suitable algorithm for solving this problem: knapsack problem

Answer 2

In general, the "de facto" algorithm for finding short paths is A* (a star).
In your case, there is also a knapsack problem, in which the order in which objects are put together is determined by the route. If there is no need to get somewhere, then the easiest way is to use the " waves " algorithm while checking the number of points and "energy".
In any case, the problem is reduced to a controlled breadth-first search .