算法如果给其余是可能

Question

输入： 硬币（值：量对），量来改变

输出：真或假

例如：

Input = {50:4, 100:1, 200:2}, 300 (I have 4 pieces of '50', 1 pieces of '100' etc), must give 300 back 
Output = True 

此示例是愚蠢的。硬币可以具有不同的值，如奇数值。

硬币不能有十进制值。

任何线索？

的伪码OK

Python的也行（首选，但不是那么重要）

编辑：

我所要求的线索，而不是完整的代码。我正在考虑一种'蛮力'方法：生成所有可能的组合，并根据我拥有的硬币数量检查它们。但它似乎并不聪明..

你有没有更好的想法如何进行？

另一个例子是：

Input = {3:2, 7:1, 10:1}, 15 
Output = False 

Answer 1

你所要求的是SAT的算法，它有一个指数的复杂性，因此，除非你有一些额外的限制，你必须做一个详尽的检查（蛮力你说过）。

您可能对功能itertools.combinations(iterable, combinations_length)感兴趣，以总结所有可能的组合。你也可以代表你的内容是这样的：{3:2, 7:1, 10:1} =>[3, 3, 7, 10]

您可以检查此文章https://en.wikipedia.org/wiki/Change-making_problem 其他选项