python - 构建字典组合以匹配 Python 中的目标总和

Question

我有一个由 N 个整数值组成的字典，如下所示:

units = {'trooper':2, 'tank':10, 'helicopter':12}

而且我还有一个目标值...比如说 120。

我正在尝试找出等式的所有可能结果:

a*units['trooper'] + b*units['tank'] + c*units['helicopter'] = 120

所以结果看起来像这样:

60*trooper
55*trooper + 1*tank
54*trooper + 1*helicopter

依此类推字典中 N 个键的所有可能组合...

我该如何着手构建它？

Answer 1

如果您知道这些问题的名称，则寻找这些问题的解决方案是最容易的。谷歌 Diophantine equations .

在 Python 世界中，您可以使用 Sympy package其中包括丢番图方程求解器。该软件包可以快速解决您的问题:

from sympy import symbols
from sympy.solvers.diophantine import diop_solve

trooper, tank, helicopter = symbols('trooper tank helicopter', integer=True)
print diop_solve(2*trooper + 10*tank + 12*helicopter - 120)

输出:

(5*t - trooper + 60, -6*t + trooper - 60, trooper)

您还可以搜索 "ways to make change"这是表达问题的另一种方式。一个相关的问题称为 The Knapsack Problem众所周知，它很难解决。求解线性丢番图方程的一般系统背后的数学有点复杂。以下是一些资源:

• http://www.math.udel.edu/~lazebnik/papers/dior1.pdf
• http://www.dcc.fc.up.pt/~apt/onlinepapers/epia97_final.pdf
• https://en.wikipedia.org/wiki/Diophantine_equation#System_of_linear_Diophantine_equations
• http://www.math.utah.edu/~carlson/hsp2004/PythonShortCourse.pdf