# Finding the best N length combination between M items

Lets say I have a few million random items. Each item has 6 attributes: Type, Cost, Strength, Stamina, Agility and Intelligence. Type is one of 4 different possibilities, the other 5 are various numbers

Now I must produce a set of 4 items where the inputs are X (the maximum cost of all items) and Y (one of the latter 4 attributes that is favored) so that

1. Each of the types is present exactly once
2. The total cost must be below a certain amount (X)
3. The attribute determined by Y must be the highest among all possible combinations

Currently I'm doing this in a brute force manner, just trying every single combination and comparing it to the current best result but its very time consuming. I was wondering if anybody knows of an algorithm or something that would cut down the execution time?

• Knapsack may indeed be NP-Complete, but note that here we have to choose exactly one item of each type. The optimal combination can be determined via exhaustive search in $O(n^{4})$ ($n$ is number of items). Whether there is a more efficient algorithm than that is of course the OPs question. – megas Mar 21 '15 at 6:08