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

StackExchange Computer Science Q#40603, answer score: 2