3
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

This problem is similar to Knapsack Problem and it is NP-Complete. You may find its proof in here

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – megas
    Mar 21, 2015 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.