I’m writing a Discord bot for an online 7th Sea campaign. Players will type something like
roll finesse 4 + weaponry 3 + 1
and the bot will spit out something like
3 raises (9+2, 8+3, 6+4, leftover 5)
The hard part is grouping the dice into raises. I would like to do this automatically. Is there a known optimal algorithm for this? I played around with a straightforward greedy approach, but I’m not convinced that it is optimal in all cases. The algorithm I’m using now is:
- Add the largest die.
- Repeatedly add the largest die that will not make the group exceed 10 (or 15, if applicable).
- If the group isn’t 10 yet, add the smallest die.
I’ve found cases where this “almost” doesn’t produce the optimal outcome, but no actual failures. Still, I’m not completely convinced. Is there any existing research on this?