如何根据特定标准找到多个数据的最佳组合？

Question

我正在尝试编写一个Python脚本,该脚本可以找到符合特定条件的游戏装甲项目组合.我有一个物品,每个物品槽都有钥匙(即头部,胸部,腰部等),以及每个钥匙中可以放入该槽位的所有物品的清单.每个项目有10个插槽和许多项目,最多可达88个项目.

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

我不相信粗暴强迫它是实用的,因为它需要很长时间(如果我错了,请纠正我).任何帮助,将不胜感激!

编辑 - 更多详情:

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

我可能想要对样本数据做的一件事就是获得头盔和胸部的组合,其总攻击/钝击/刺穿总数最多,但总阻力小于12.

Answer 1

听起来这个问题的优雅解决方案是线性编程。如果您提供更多详细信息，我可以提供帮助。

由于只有 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))

请注意，您应该将值存储为浮点数而不是字符串！转换为字符串比浮点数更容易（因为在需要时它通常是自动的）。然后你就可以从我的代码中去掉丑陋的强制转换。我只是懒得为你做。请注意，您可以使用任意数量的约束进行调用，但只能最大化一组属性。这对我来说很有意义。如果您研究代码并理解它，您应该能够修改它以适合您的口味。

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

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

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