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


Each of the types is present exactly once
The total cost must be below a certain amount (X)
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?
This problem is similar to Knapsack Problem and it is NP-Complete. You may find its proof in here