Path finding to collect enough items before the fight with the enemy

So I have the following problem : a X by Y grid. On the grid there is a character and a monster and some items that give bonus points to the character's damage if picked and holes that must be avoided. The goal is to collect enough items to be able to defeat the monster, then navigate to the monster and fight it.

What kind of algorithm can be used to solve this problem?

• Are you talking about turn based or real time gameplay? Have you considered looking at A*? The implementation looks difficult but is actually pretty simple. – Sidar Apr 2 '13 at 10:53
• Game play is real time. – user25894 Apr 2 '13 at 10:59
• Ok, you could leave some info out of your question btw. The focus here is to achieve pathfinding. Right? I'd say look at A*. – Sidar Apr 2 '13 at 11:52
• But I have to choose the path that collects enough powerups to be able to defeat the monster. – user25894 Apr 2 '13 at 12:18
• @Trevor: close. If the asker needs the shortest such path, it's a collection of Hamiltonian path problems. If there are n items and k are needed, then there are (n Choose k) subsets to find a Hamiltonian path through, plus the start and end legs to connect to the player and monster positions. TLDR: approximate, maybe greedily. The optimum's probably too much work. – DMGregory Mar 9 '14 at 21:50