4

我正在尝试编写一个脚本，该脚本将采用一个项目字典，每个项目包含 0 到 10 的值的属性，并添加各种元素以选择哪些项目组合达到所需的总数。我还需要脚本来执行此操作，仅使用具有相同“插槽”的项目。

例如：

item_list = {
 'item_1': {'slot': 'top', 'prop_a': 2, 'prop_b': 0, 'prop_c': 2, 'prop_d': 1 },
 'item_2': {'slot': 'top', 'prop_a': 5, 'prop_b': 0, 'prop_c': 1, 'prop_d':-1 },
 'item_3': {'slot': 'top', 'prop_a': 2, 'prop_b': 5, 'prop_c': 2, 'prop_d':-2 },
 'item_4': {'slot': 'mid', 'prop_a': 5, 'prop_b': 5, 'prop_c':-5, 'prop_d': 0 },
 'item_5': {'slot': 'mid', 'prop_a':10, 'prop_b': 0, 'prop_c':-5, 'prop_d': 0 },
 'item_6': {'slot': 'mid', 'prop_a':-5, 'prop_b': 2, 'prop_c': 3, 'prop_d': 5 },
 'item_7': {'slot': 'bot', 'prop_a': 1, 'prop_b': 3, 'prop_c':-4, 'prop_d': 4 },
 'item_8': {'slot': 'bot', 'prop_a': 2, 'prop_b': 2, 'prop_c': 0, 'prop_d': 0 },
 'item_9': {'slot': 'bot', 'prop_a': 3, 'prop_b': 1, 'prop_c': 4, 'prop_d':-4 },
}

然后，脚本需要从“item_list”dict 中选择每个“slot”使用 1 个项目的组合，以便在添加时达到预期的结果。

例如，如果期望的结果是：'prop_a': 3, 'prop_b': 3, 'prop_c': 8, 'prop_d': 0, 脚本会选择 'item_2', 'item_6' 和 'item_9',以及任何其他有效的组合。

'item_2': {'slot': 'top', 'prop_a': 5, 'prop_b': 0, 'prop_c': 1, 'prop_d':-1 }
'item_6': {'slot': 'mid', 'prop_a':-5, 'prop_b': 2, 'prop_c': 3, 'prop_d': 5 }
'item_9': {'slot': 'bot', 'prop_a': 3, 'prop_b': 1, 'prop_c': 4, 'prop_d':-4 }
 'total':                 'prop_a': 3, 'prop_b': 3, 'prop_c': 8, 'prop_d': 0

任何想法如何做到这一点？它不需要在 python 中，甚至不需要一个完整的脚本，但对我来说，理论上如何做到这一点的解释就足够了。我已经尝试过遍历每个组合，但这似乎很快就让我们掌握了并且无法管理。实际脚本将需要使用 20 个不同的“插槽”对大约 1,000 个项目执行此操作，每个“插槽”具有 8 个属性。

谢谢您的帮助！

4

4 回答 4

7

由于属性可以具有正值和负值，并且您需要所有令人满意的组合，我相信没有“必要”优化可能 - 也就是说，没有多项式时间解决方案（假设 P ！= NP ...;-) . 所有解决方案都将归结为枚举所有每个插槽一个组合并检查最终结果，可能会进行非常小的调整，这可能会在这里或那里为您节省一些工作量，但没什么大不了的。

如果您在 20 个可能的插槽中有 1000 个项目，例如平均分布在每个插槽大约 50 个项目，那么50**20总体上存在大约可能性，即9536743164062500000000000000000000- 大约10**34（数以亿计的数十亿......）。通常，您不能从“所有解决方案搜索”中“修剪”任何子树，因为当您假设第一个插槽的选择时，无论道具值如何20-p，仍然可能会选择剩余的p插槽可以满足约束（或多个）。

如果你能找到一个精确的多项式时间解决方案，一个 NP 完全问题，你基本上已经彻底改变了现代数学和计算机科学——图灵奖和菲尔兹奖只是随之而来的荣誉的开始。这不太可能。

为了解决一个可行的问题，您必须在某些方面放宽您的要求（接受仅找到解决方案子集的可能性，接受概率而不是确定性方法，接受近似解决方案，......）。

一旦你这样做了，一些小的优化可能是有意义的——例如，从对所有属性值和目标求和常量（等于每个属性的最小负值大一）开始，以便每个属性值 > 0 - - 现在您可以按（例如）某些属性的值或所有属性的总和对插槽进行排序，并根据以下知识进行一些修剪：在部分假设解决方案中再添加一个插槽将使每个累积道具值至少增加X 和至少 Y 的总数（因此，如果任一条件使运行总数超过目标，您可以修剪该分支）。一般来说，这种启发式近似不需要使大 O 行为变得更好，但它可以将预期乘数值降低到足以使问题更接近计算上可行。

但是，如果不可能放宽要求，那么甚至不值得寻找这样聪明的小技巧：在这种情况下，问题将在计算上保持不可行，因此寻找聪明的小优化无论如何都不会有效。

于 2010-04-25T17:34:18.757 回答
4

这个问题本质上是将子集和问题（是 NP 完全的，是的）推广到多个维度。重申问题（以确保我们正在解决相同的问题）：您有 1000 个项目，分为 20 个类别（您称之为插槽）。对于 8 个属性中的每一个，每个项目在 [-10,10] 中都有一个整数值；因此，每个项目都可以被认为具有一个 8 维向量的值。您想从每个插槽中选择一个项目，以便总值（添加这些 8 维向量）是一个给定的向量。

在您给出的示例中，您有 4 个维度，并且 3 个类中的 9 个项目具有值 (2,0,2,1)、(5,0,1,-1) 等，并且您要选择每个类别中的一项以得出总和（3,3,8,0）。正确的？

蛮力

首先，存在列举所有可能性的蛮力搜索。假设您的 1000 个项目平均分为 20 个类别（因此每个类别有 50 个），每个类别有 50 个选项，这意味着您必须检查 50 20 =95367431640625000000000000000000000 个选项（对于每个选项，您需要将 8 个坐标中的每一个的 20 个元素相加并检查，因此运行时间为∝ 50 20 ·20·8)：这是不可行的。

动态规划，单次

然后是动态编程解决方案，它是不同的，在实践中经常在蛮力不可行的情况下工作，但不幸的是，在这种情况下似乎也不可行。（如果你的“属性值”有更好的界限，你会成倍地改进它。）这里的想法是跟踪达到每个可能sum的一种方法。来自 [-10,10] 的 20 个数字之和位于 [-200,200]，因此“只有”400 8=655360000000000000000 8 维向量的可能总和。（这只是其他搜索空间的一小部分，但这对您来说并不安慰。您还可以为每个“属性”获取 [每个类别中的最大项目] 和 [每个类别中的最小项目] 之和之间的差异] 用较小的数字替换 400。）动态规划算法的思想如下。

  • 让 last[(a,b,c,d,e,f,g,h)][k] 表示您可以从第 k 类中获取的一项（以及前 k-1 类中的一项）总和（a，b，c，d，e，f，g，h）。然后，伪代码：

    for k=1 to 20:
    for each item i in class k:
        for each vector v for which last[v][k-1] is not null:
            last[v + value(i)][k] = i

然后，如果您想要的最终总和是 s，则从第 k 个类中选择项目 last[s][k]，从第 (k-1) 个类中选择项目 last[s-value(i)][k-1]，等等。在最坏的情况下，这需要时间∝ 20·50·400 8 ·8（只是一个宽松的上限，而不是严格的分析）。

动态规划，单独

“完美”的解决方案就这么多。但是，如果您允许启发式解决方案和那些“最有可能在实践中工作”的解决方案，您可以做得更好（即使是为了准确地解决问题）。例如，您可以针对 8 个维度中的每一个维度分别解决问题。这更容易实现，在最坏的情况下只需要时间∝ 20·50·400·8=3200000，而且你可以很容易地做到。如果您将 last[][] 保留为列表，而不是单个元素，那么最后您将（有效地）获得一个子集列表，这些子集可以达到给定的总和坐标（以“产品形式”）。在实践中，没有多少子集可以完全加起来您想要的总和，因此您可以从子集数量最少的坐标开始，然后尝试其他 7 个坐标中的每个子集。此步骤的复杂性取决于问题中的数据，但我怀疑（或希望）任一（1）将有非常少的集合具有相等的和，在这种情况下，这个交集将减少集合的数量到检查，或者 (2) 会有很多集合具有给定的总和，在这种情况下你会很早就找到一个。

无论如何，首先对每个坐标分别进行动态规划肯定会让您在第二阶段搜索更小的空间。

近似算法

If you don't need the sums to be exactly equal and will accept sums that are within a certain factor of your required sum, there is a well-known idea used to get an FPTAS (fully polynomial-time approximation scheme) for the subset-sum problem, which runs in time polynomial in (number of items, etc.) and 1/ε. I've exhausted my time to explain this, but you can look it up — basically, it just replaces the 4008 space by a smaller one, by e.g. rounding numbers up to the nearest multiple of 5, or whatever.

于 2010-04-25T20:11:39.040 回答
3

这听起来像是背包问题的变体，通常用动态规划来解决。

但是，您可能可以使用递归编写一个相当简单的解决方案（但速度较慢）：

def GetItemsForSlot(item_list, slot):
  return [ (k,v) for (k,v) in item_list.items() if v['slot'] == slot]

def SubtractWeights(current_weights, item_weights):
  remaining_weights = {}
  for (k,v) in current_weights.items():
      remaining_weights[k] = current_weights[k] - item_weights[k]
  return remaining_weights

def AllWeightsAreZero(remaining_weights):
  return not [v for v in remaining_weights.values() if v != 0]

def choose_items(item_list, remaining_weights, available_slots,
                 accumulated_items=[ ]):
    print "choose_items: ", remaining_weights, available_slots, \
      accumulated_items
    # Base case: we have no more available slots.
    if not available_slots:
      if AllWeightsAreZero(remaining_weights):
          # This is a solution.
          print "SOLUTION FOUND: ", accumulated_items
          return
      else:
          # This had remaining weight, not a solution.
          return

    # Pick the next available_slot
    slot = available_slots[0]
    # Iterate over each item for this slot, checking to see if they're in a
    # solution.
    for name, properties in GetItemsForSlot(item_list, slot):
        choose_items(item_list, # pass the items recursively
                     SubtractWeights(remaining_weights, properties),
                     available_slots[1:], # pass remaining slots
                     accumulated_items + [name]) # Add this item




if __name__ == "__main__":
    total_weights = {
       'prop_a': 3,
       'prop_b': 3,
       'prop_c': 8,
       'prop_d': 0
    }

    choose_items(item_list, total_weights, ["top", "mid", "bot"])

这是经过测试的，并且似乎有效。虽然没有承诺:)

将 slot 和 prop_a 保留为同一个对象的属性使其更难使用。我建议使用类而不是字典来使代码更容易理解。

于 2010-04-25T16:47:16.953 回答
1

我已经尝试过遍历每个组合，但这似乎很快就让我们掌握了并且无法管理。实际脚本将需要使用 20 个不同的“插槽”对大约 1,000 个项目执行此操作，每个“插槽”具有 8 个属性。

首先将结构加载到一个很好的对象层次结构中，然后分段求解，这可能有助于您的思考。

例子：

class Items(dict):
    def find(self, **clauses):
        # TODO!

class Slots(dict):
    # TODO!

items = Items()
for item, slots in item_list.items():
    items[item] = Slots(slots)
    # consider abstracting out slot based on location (top, mid, bot) too

print items.find(prop_a=3, prop_b=3, prop_c=8, prop_d=0)
于 2010-04-25T17:01:14.640 回答