计算字典中的添加组合的Python脚本

Question

我正在尝试写一个脚本，这个脚本需要处理一个字典，字典里有很多物品，每个物品都有一些属性，属性的值在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”字典中选择组合，每个“槽位”只能用一个物品，最终加起来能达到我想要的结果。

比如，如果我想要的结果是：'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，也不需要一个完整的脚本，只要能理论上解释一下怎么做就行。我尝试过遍历每一种组合，但这似乎很快就变得复杂且难以管理。实际上，这个脚本需要处理大约1000个物品，使用20个不同的“槽位”，每个槽位都有8个属性。

谢谢你的帮助！

Answer 1

这听起来像是一个变种的 背包问题，通常可以用 动态规划 来解决。

不过，你也可以用递归的方法写一个相对简单的解决方案（虽然速度会慢一些）：

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 作为同一个对象的属性会让处理起来有点困难。我建议用类来代替字典，这样代码会更容易理解。

Answer 2

这个问题其实是一个更复杂的版本，叫做子集求和问题（这个问题是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²⁰=9536743164062500000000000000000000种选择（而且每种选择你还需要把20个元素在8个坐标上加起来并进行检查，所以运行时间大约是∝ 50²⁰·20·8）：这显然是不可行的。

动态规划，单次处理

接下来是动态规划的解决方案，这种方法不同，实际上在暴力搜索不可行的情况下，动态规划通常能奏效，但在这个例子中，遗憾的是也似乎不可行。（如果你能更好地界定“属性值”的范围，你会大大提高效率。）这里的想法是跟踪到达每个可能的和的一种方法。20个来自[-10,10]的数字的和在[-200,200]之间，所以你的8维向量的可能和“只有”400⁸=655360000000000000000可能（这只是其他搜索空间的一个小部分，但对你来说并没有安慰）。你也可以对每个“属性”计算[每个类别中最大物品的和]和[每个类别中最小物品的和]之间的差值，从而把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个维度解决这个问题。这种方法实现起来更简单，最坏情况下只需时间∝ 20·50·400·8=3200000，而且你可以很轻松地做到。如果你把last[][]作为一个列表，而不是单个元素，那么最后你就会得到一个（实际上是）实现给定和的子集列表（以“乘积形式”表示）。在实践中，并不是很多子集会恰好加起来等于你想要的和，所以你可以先从子集数量最少的坐标开始，然后尝试这些子集在其他7个坐标上的表现。这个步骤的复杂度取决于问题中的数据，但我怀疑（或者说希望）要么（1）会有很少的集合具有相同的和，这样交集会减少需要检查的集合数量，要么（2）会有很多集合具有给定的和，这样你会很快找到一个。

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

近似算法

如果你不需要和完全相等，而是接受在某个范围内的和，有一个著名的想法可以用来得到子集求和问题的FPTAS（完全多项式时间近似方案），它的运行时间是多项式级别的（物品数量等）和1/ε。我已经没有时间详细解释这个了，但你可以查一下——基本上，它只是通过例如将数字四舍五入到最接近的5的倍数，或者其他方式，来将400⁸的空间替换为更小的空间。

Answer 3

因为这些属性可以有正值和负值，而且你需要找到所有满意的组合，所以我认为没有什么“根本”的优化方案可行——也就是说，没有多项式时间的解决方案（假设 P 不等于 NP...;-）。所有的解决方案都要通过列举每个位置的组合，然后检查最终结果，虽然可能有一些小的调整可以节省一点点时间，但没有什么大的突破。

假设你有1000个物品要放在20个位置上，每个位置大约有50个物品，那么总的可能性大约是 50**20，也就是 9536743164062500000000000000000000 —— 大约是 10**34（数以亿亿亿计的数量）。一般来说，你无法从“所有解决方案的搜索”中“剪枝”，因为无论属性值是什么，当你假设选择了前 20-p 个位置时，剩下的 p 个位置仍然可能有选择满足条件（或者不止一个）。

如果你能找到一个确切的多项式时间解决方案来解决这个 NP 完全问题，那你基本上就会彻底改变现代数学和计算机科学——图灵奖和菲尔兹奖只是开始，后续的荣誉会接踵而来。但这并不太可能。

为了让问题变得可行，你需要在某些方面放宽要求（接受只找到部分解决方案的可能性，接受概率性而不是确定性的方法，接受近似解决方案，等等）。

一旦你这样做了，一些小的优化可能会有意义——例如，先把常数（等于每个属性的最小负值加一）加到所有属性值和目标上，这样每个属性值就都大于0——现在你可以根据某个属性的值或所有属性的总和来对位置进行排序，并根据添加一个位置到部分假设解决方案会使每个累积属性值至少增加X和总值至少增加Y的知识进行一些剪枝（如果任何条件使得运行总数超过目标，你就可以剪掉那条分支）。这种启发式的近似方法一般来说不一定会改善大O行为，但可能会降低预期的乘数值，从而使问题更接近于可计算的可行性。

但是，如果没有放宽要求的可能性，寻找这种聪明的小技巧就没有意义：在这种情况下，问题将保持计算上不可行，因此寻找聪明的小优化也不会有实际的效果。