How to find the best combination of many pieces of data depending on certain criteria?

Question

I am trying to write a Python script that finds combinations of armor items from a game that match certain criteria. I have an object that has keys for each item slot (ie. head, chest, waist, etc.) and a list of all the items that can fit in that slot with their stats in each key. There are 10 slots and many items for each up to a total of 88 or so items.

My question is: Is there some kind of algorithm already used to do stuff like this? An example of what I would want to do is find the combination of armor pieces that gives me stat1 < 35 that has the highest stat2+3+4.

I don't believe brute forcing it would be practical because it would take ages (correct me if I'm wrong). Any help would be appreciated!

Edit - More details:

Data sample: http://pastebin.com/rTH3Q5Sj The first tuple is 2 head slot items, 2nd tuple is 2 chest slot items.

One thing I might want to do with the sample data is get the combination of helm and chest that has the highest slashing/bludgeoning/piercing total but less than 12 encumbrance total.

Answer 1

It sounds like the elegant solution to this is linear programming. I can help with that if you provide more details.

with only 88 items spread out amongst ten slots, brute forcing it wouldn't be terrible either. Some combination of the two might be the easiest.

update:

based on the update you gave, I think linear programming is overkill (and difficult to apply). I wrote you this fairly general solution. Study it and understand it. If anybody has any corrections or improvements, I'd love to hear them.

from itertools import ifilter, product

# Definition of ITEMS cut for brevity. See below.    

def find_best(slots, maximize, constraints):
    """example call:
         find_best(['helm', 'chest'], ['slashing', 'bludgeon'],
                   {'encumbrance': 12})
    """
    # save the slot names to construct a nice return value
    slot_names = slots

    # pull the actual lists of items for each slot out of the global dict
    slots = [ITEMS[slot] for slot in slots]

    # this function calculates the value of a solution
    value = lambda solution: sum(float(slot[attr]) for attr in maximize
                                                   for slot in solution)

    # replace our constraints with functions to check solutions
    constraints = [lambda solution:
                       sum(float(slot[attr]) for slot in solution) < constraint
                 for attr, limit in constraints.items()]

    # start with all possible combinations
    solutions = product(*slots)

    # chain together ifilters to weed out the ones that fail any of the
    # constraints. Note that for optimum performance, you should place the
    # constraints in descending order of probability to fail
    for constraint in constraints:
        solutions = ifilter(constraint, solutions)

    # We're going to do decorate, max, undecorate
    solutions = ((value(solution), solution) for solution in solutions)
    value, solution = max(solutions)

    # get the indexes and return
    return dict((name, slot.index(item)) for name, slot, item
                in zip(slot_names, slots, solution))

Note that you should be storing the values as floats and not as strings! It's easier (because it's often automatic when you need it) to cast to string than a float. Then you can take the ugly casts out of my code. I was just to lazy to do it for you. Note that you can call with as many constraints as you want but only one set of attributes to maximize. This made sense to me. If you study the code and understand it, you should be able to modify it to suit your tastes.

Here's how I modified your data structure.

ITEMS = { 'helm': [{'Acid':' 2.71',
                        'Bludgeoning': '1.04',
                        'Cold': '2.71',
                        'Encumbrance': '8.00',
                        'Fire': '2.71',
                        'Holy': '2.71',
                        'Impact': '1.30',
                        'Lightning': '2.00',
                        'Name': 'Plate Helm',
                        'Piercing': '1.17',
                        'Slashing': '1.30',
                        'Unholy': '2.71'},

                       {'Acid': '2.18',
                        'Bludgeoning': '0.92',
                        'Cold': '2.18',
                        'Encumbrance': '7.00',
                        'Fire': '2.18',
                        'Holy': '2.18',
                        'Impact': '1.15',
                        'Lightning': '1.65',
                        'Name': 'Scale Helm',
                        'Piercing': '1.03',
                        'Slashing': '1.15',
                        'Unholy': '2.18'}],

              'chest':[{'Acid': '5.47',
                        'Bludgeoning': '2.05',
                        'Cold': '5.47',
                        'Encumbrance': '32.00',
                        'Fire': '5.47',
                        'Holy': '5.47',
                        'Impact': '2.57',
                        'Lightning': '4.06',
                        'Name': 'Plate Chest',
                        'Piercing': '2.31',
                        'Slashing': '2.57',
                        'Unholy': '5.47'},

                       {'Acid': '4.45',
                        'Bludgeoning': '1.84',
                        'Cold': '4.45',
                        'Encumbrance': '28.00',
                        'Fire': '4.45',
                        'Holy': '4.45',
                        'Impact': '2.30',
                        'Lightning': '3.31',
                        'Name': 'Scale Cuirass',
                        'Piercing': '2.07',
                        'Slashing': '2.30',
                        'Unholy': '4.45'}]}

note that the values of the outermost dictionary are lists and not tuples as you said. There is a huge distinction!

Answer 2

Seems like a variation of the Knapsack problem. Dynamic programming should be good enough if your weight (stats?) limit is not too big.

Edit:

Here's a prototype in Java of the dynamic programming solution:

public static int getBestAcidSum(int[][] acid, int[][] fire, int maxFire) {
    int slots = acid.length;
    int[][] acidSum = new int[slots][maxFire + 1];

    for (int j = 0; j < acid[0].length; j++)
        acidSum[0][fire[0][j]] = Math.max(acidSum[0][fire[0][j]], acid[0][j]);

    for (int i = 1; i < slots; i++)
        for (int j = 0; j < acid[i].length; j++)
            for (int fireSum = fire[i][j]; fireSum <= maxFire; fireSum++)
                if (acidSum[i-1][fireSum - fire[i][j]] > 0)
                    acidSum[i][fireSum] = Math.max(acidSum[i][fireSum], acidSum[i-1][fireSum - fire[i][j]] + acid[i][j]);

    int ret = 0;
    for (int fireSum = 0; fireSum <= maxFire; fireSum++)
        ret = Math.max(ret, acidSum[slots - 1][fireSum]);
    return ret;
}

public static void main(String[] args) {
    System.out.println(getBestAcidSum(new int[][] {{271, 218},  {547, 445}}, new int[][] {{271, 218}, {547, 445}}, 800));
}

The algorithm is O(N*C) where N is the total number of items and C is the constraint ("maxFire" in the example). Should work instantaneously with the quantities you've been mentioning.

The code is very simplified but it maintains the fundamental algorithmic difficulty. It only returns the optimal sum that fulfills the constraints. Should be easily modified to return the actual combination. Summing more than one stat together should be easily incorporated as well. Values were converted to integers by multiplying by 100.