algorithm - 如何根据一定的标准找到多条数据的最佳组合？

Question

我正在尝试编写一个 Python 脚本，从游戏中查找符合特定条件的盔甲元素组合。我有一个对象，它有每个项目槽(即头部、胸部、腰部等)的键，以及可以放入该槽的所有项目的列表，每个键都有它们的统计信息。有 10 个槽位，每个槽位有许多元素，总共有 88 个左右的元素。

我的问题是:是否已经使用某种算法来做这样的事情？我想要做的一个例子是找到给我 stat1 < 35 的盔甲组合，它具有最高的 stat2+3+4。

我不相信暴力破解是可行的，因为它需要很长时间(如果我错了请纠正我)。任何帮助将不胜感激!

编辑 - 更多细节:

数据样本:http://pastebin.com/rTH3Q5Sj第一个元组是 2 个头部槽项目，第二个元组是 2 个胸部槽项目。

我可能想对样本数据做的一件事是获得具有最高挥砍/钝击/穿刺总数但少于 12 种负担的 Helm 和胸部组合。

Answer 1

听起来优雅的解决方案是 linear programming .如果您提供更多详细信息，我可以提供帮助。

只有 88 个项目分布在 10 个插槽中，暴力破解也不会很糟糕。两者的某种组合可能是最简单的。

更新:

根据您提供的更新，我认为线性规划是矫枉过正(并且难以应用)。我给你写了这个相当通用的解决方案。研究它并理解它。如果有人有任何更正或改进，我很乐意听取他们的意见。

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))

请注意，您应该将值存储为 float 而不是不是字符串!转换为字符串比转换为 float 更容易(因为它通常在您需要时自动进行)。然后你可以从我的代码中删除丑陋的转换。我只是懒得为你做这件事。请注意，您可以调用任意多的约束，但只能最大化一组属性。这对我来说很有意义。如果您研究并理解了代码，您应该能够根据自己的喜好对其进行修改。

这是我修改你的数据结构的方式。

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'}]}

请注意，最外层字典的值是列表而不是您所说的元组。有很大的区别!