判定是否可以给予休息的算法

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

这个例子是愚蠢的。硬币可以有不同的价值，比如奇数价值。你知道吗

硬币不能有小数。你知道吗

有线索吗？你知道吗

伪代码正常

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 对于其他选项