In role playing games, switching equipment for better is a common procedure. My question is to find an algorithm that can optimize linear combination of stats the equipped gear gives - this is exactly how it works on The-West.net:
- Each piece of equipment can be equipped in only one slot (there is approximately 5-10 of each)
- The evaluation function is parametrized, but can be pre-processed by assigning to each gear a score (as a linear combination of the stats it gives), therefore the objective is to simply maximize the score.
- No equipment has a negative score.
With this specification, the calculation is simple: for each slot, find the best gear individually.
What complicates the problem is following:
- Each gear can be assigned into one set at most.
- Having multiple gear of the same set gives extra stats (score) based on the amount of gear equipped, not on its types.
- The set bonus is nondecreasing (wrt amount of equipped gear)
- Multiple equipped sets can produce more bonuses independently.
- Multiple gear of the same slot can belong to the same set.
My attempts so far:
A gear which does not belong to any set can be easily eliminated, unless it is the best in its own slot. The same can be said about gear for the same slot within the same set.
Greedy/dynamic solution slot-by-slot does not work. Suppose these comparisons (unit used is the final score):
Pants_A > Pants_B
Hat A > Hat B
Pants_A + Hat_A + Set(A,2) < Pants_B + Hat_B + Set(B,2)
The plugin can apparently also calculate for score with non-linear relationships, but the solution there is explicitly said to be heuristical. Which means that solutions based on set partition (find best gear without any sets ... find best gear with two 4-piece sets ...) would be too slow overkill for this case.
Edit: I have realized that even the pre-processing relies on the non-diminishing stat returns. So when using brute-force, the complexity is "only" $O(s^p)$ , where s is amount of sets (+1 for no set) and p amount of slots, assuming the evaluation fn is constant. But it would obviously still be better to find something more efficient.
Thanks for any help.