Python脚本来计算字典交锋组合 [英] Python script to calculate aded combinations from a dictionary

问题描述

我试图写一个脚本，将采取一本字典的项目，从0值的每个包含的属性 - 10，并添加各种元素来选择项目组合，达到理想的总数。我还需要脚本做到这一点，只利用具有共同的相同的槽的项目。

I am trying to write a script that will take a dictionary of items, each containing properties of values from 0 - 10, and add the various elements to select which combination of items achieve the desired totals. I also need the script to do this, using only items that have the same "slot" in common.

例如：

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字典选择哪个组合是增加使用时按插槽1项，将达到想要的结果。

The script would then need to select which combinations from the "item_list" dict that using 1 item per "slot" that would achieve a desired result when added.

例如，如果所需的结果是：'prop_a'：3'，prop_b'：3'，prop_c'：8'，prop_d'：0，脚本将选择'item_2'，'item_6'，和' item_9'，连同工作的任何其他组合。

For example, if the desired result was: 'prop_a': 3, 'prop_b': 3, 'prop_c': 8, 'prop_d': 0, the script would select 'item_2', 'item_6', and 'item_9', along with any other combination that worked.

'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

任何想法如何做到这一点？它并不需要在蟒蛇，甚至是彻底的脚本，但只是如何做到这一点在理论上的解释是足够了。我试图制定通过每个组合循环，但似乎很快得到我们的手，无法控制。实际的脚本将需要做到这一点，使用20种不同的槽，每个有8个属性约1,000个项目。

Any ideas how to accomplish this? It does not need to be in python, or even a thorough script, but just an explanation on how to do this in theory would be enough for me. I have tried working out looping through every combination, but that seems to very quickly get our of hand and unmanageable. The actual script will need to do this for about 1,000 items using 20 different "slots", each with 8 properties.

感谢您的帮助！

推荐答案

由于属性可以有正反两方面的价值，你需要的所有的理想组合，我相信没有必要优化可能 - 即无多项式时间解（假定P = NP ... ;-)！。所有的解决方案将下降到枚举所有单每插槽组合和检查的最终结果，具有非常小的调整可能会在这里或那里为您节省一些％的努力，但没有真正的大。

Since the properties can have both positive and negative values, and you need all satisfactory combinations, I believe there is no "essential" optimization possible -- that is, no polynomial-time solution (assuming P != NP...;-). All solutions will come down to enumerating all the one-per-slot combinations and checking the final results, with very minor tweaks possible that may save you some percent effort here or there, but nothing really big.

如果你有1000个项目在20个可能的插槽，说平均分配每插槽约50个项目，大约有 50 ** 20 可能性整体，即 9536743164062500000000000000000000 - 关于 10 ** 34 （无数十亿百亿千亿...）。你不能，在一般情况下，修剪，从全解决方案搜索任何树，因为无论道具值，当你有一个假设挑的第一个 20-P 插槽，仍有的也许的是挑剩下的 P 插槽，能够满足约束条件（或多个）。

If you have 1000 items in 20 possible slots, say equally distributed at about 50 items per slot, there are around 50**20 possibilities overall, i.e, 9536743164062500000000000000000000 -- about 10**34 (a myriad billions of billions of billions...). You cannot, in general, "prune" any subtree from the "all-solutions search", because no matter the prop values when you have a hypothetical pick for the first 20-p slots, there still might be a pick of the remaining p slots that could satisfy the constraint (or, more than one).

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

If you could find an exact polynomial-time solution for this, a NP-complete problem, you'd basically have revolutionized modern mathematics and computer science -- Turing prizes and Field medals would only be the start of the consequent accolades. This is not very likely.

要踏踏实实地一个可行的问题，你必须放松您的要求在某些方面（接受找出解决方案的一个子集的可能性，接受概率，而不是确定性的方法，接受近似解，... ）。

To get down to a feasible problem, you'll have to relax your requirements in some ways (accept the possibility of finding just a subset of the solutions, accept a probabilistic rather than deterministic approach, accept approximate solutions, ...).

一旦你这样做，一些小的优化可能是有意义的 - 例如，开始总结常数（等于一个超过每礼的最小负值）的所有属性值和目标，让每一个道具值> 0 - 现在你可以通过插槽（例如）值对于某些属性或所有属性的总和进行排序，并以此为基础进行再增加一个插槽部分假设的解决方案将增加每累计道具价值的认识了一些修剪至少X和总量至少Y（这样你就可以修剪分支，如果任何一个条件，使运行总计超过目标）。这种启发式近似不需要做任何更好大O行为，在一般情况下，但也可以降低由足够预期乘数值以获得该问题更接近于计算上是可行的。

Once you do, some small optimizations may make sense -- for example, start with summing constants (equal to one more than the smallest negative value of each propriety) to all the property values and targets, so that every prop value is > 0 -- now you can sort the slots by (e.g.) value for some property, or the sum of all properties, and do some pruning based on the knowledge that adding one more slot to a partial hypothetical solution will increase each cumulative prop value by at least X and the total by at least Y (so you can prune that branch if either condition makes the running totals exceed the target). This kind of heuristic approximation need not make the big-O behavior any better, in general, but it may reduce the expected multiplier value by enough to get the problem closer to being computationally feasible.

但是，这不值得寻找这样聪明的小动作，如果没有规定的放松可能。在这种情况下，问题会留下来计算不可行的，所以寻找聪明的小的优化不会实际生产反正

But it's not even worth looking for such clever little tricks if there's no requirement relaxation possible: in that case, the problem will stay computationally unfeasible, so looking for clever little optimizations would not be practically productive anyway.

这篇关于Python脚本来计算字典交锋组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！