Lets say I have a few million random items. Each item has 6 attributes: Type, Co

Question

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?

Explanation / Answer

This problem is similar to Knapsack Problem and it is NP-Complete.

To understand NP-completeness, you have to learn a bit of complexity theory: you ain't gonna get that from SO! However, basically, it's NP-complete because an efficient algorithm for the knapsack problem would also be an efficient algorithm for SAT, TSP and the rest.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.