In the last 4 months I've been playing Puzzle & Dragons, I've frequently found myself in one of two similar situations:

• I need 9,842 EXP to rank up. What dungeons should I run to rank me up?
• I have 22 stamina to use up before bed. Which dungeons should I run to spend it most efficiently?

And each time, I would pull up my go-to reference page on PDX and browse through it, looking for the best combination of dungeons. After a while of doing this, I decided a tool should exist to make this process easier and better.

A Puzzling problem

Finding the most EXP-efficient dungeons is relatively simple for lower stamina amounts. Here's a chart of which dungeon is the best for stamina amounts less than 17:

But for larger stamina amounts, the problem of figuring out the most efficient combination of dungeons can be surprisingly tricky. The reason for this is because choosing which dungeon to run in PAD is a resource-allocation problem that falls under a category called Knapsack problems. Briefly described, knapsack problems are situations where an array of choices are available. Each choice has an associated value (EXP in this case) and an associated cost (Stamina in this case). The problem is how to stuff your knapsack of a certain fixed total size with the choices available to maximize the total value.

Knapsack problems are interesting in computer science and mathematics primarily because they are hard to solve. Optimizing and solving for the ideal solution is NP-hard, meaning no algorithm exists that is "fast" in its run-time. Put another way, the run-time for finding the solution for an arbitrarily large knapsack, with an arbitrarily large number of choice scales (more or less) exponentially!

Fortunately, the world of PAD is not arbitrarily large, but is in fact constrained to 166 Dungeons (167 if you count Celestial Black Dragon). And so, solving for just these dungeons and any reasonably large stamina amount is more than doable, even in our dinky browsers or mobile devices.

If you're curious, here's a quite readable description of the actual algorithm to solve the problem we've described so far: http://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem

Isn't average EXP/stamina enough?

While average EXP/stamina is a good measure of a dungeon's efficiency, it is only effective in selecting a dungeon when you have an infinite amount of stamina.

For example, if you haven't cleared Starlight Sanctuary yet (like me), the most efficient, highest EXP/stamina dungeon is Hyperion Lava Flow - Lava Tube. It costs 10 stamina to run. If you had 25 stamina, here are 2 options:

Option 1:

Hyperion Lava Flow - Lava Tube           10 Stamina     5,276 EXP    528 EXP/Stam
Hyperion Lava Flow - Lava Tube           10 Stamina     5,276 EXP    528 EXP/Stam
Tower of Giants - Dragons of the Tower    5 Stamina     1,542 EXP    308 EXP/Stam

Total:                                   25 Stamina    12,094 EXP

Option 2:

Frozen Soil of Prosell - Frozen Ground   13 Stamina     6,745 EXP    519 EXP/Stam
Kronos Forest - Ancient Guardian         12 Stamina     6,307 EXP    526 EXP/Stam

Total:                                   25 Stamina    13,052 EXP

Here we see that simply trying to run the highest EXP/Stam dungeons first is not always the most efficient solution. Even though Lava Tube is the single most efficient EXP/Stam dungeon, it is better in this scenario to "stuff your knapsack" with a 13-stamina and a 12-stamina dungeon.

Now, this isn't always the case. Many times it is most efficient to run the highest EXP/Stam dungeons. There simply is no rule-of-thumb that works in every situation for choosing the best dungeons to stuff your knapsack. That's also the trickiness behind these knapsack problems.
The solution? Just let the Rank Up calculator find the optimum solution for you :).

Enough talk!

Give the calculator a try here: http://tamadra.github.io/rank-up

Feedback and reporting any bugs would be much appreciated. Either add a comment below, or contact me on reddit, twitter or github.

Thanks for reading!