算法如果給其餘是可能

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 其他選項