这是一个被称为“邮票问题”的数学问题。您需要在信封上贴上一定数量的邮资(数量)。 信封上只有 n 个邮票的空间(但不能更多)。
有可用邮票面额的列表 (denominations)。您可以根据需要使用任意数量的每种面额。目标是用 面额 和限量 n 邮票获得所需的数量。
例如对于amount =12, n =3, and denominations =<<9 5 2>> 你可以这样做5+5+2。但是你根本做不到 amount =17。
我怎样才能递归地解决这个问题?
我已经能够确定基本情况。例如,当你超过了值(value)限制,或者你没有地方盖章,这些都是失败的尝试,当你达到目标时,那是一个积极的尝试,应该返回 true。 递归的技巧是找到所有可能组合的总和。
Java 中的算法或代码的轻微提示将不胜感激。
最佳答案
这是一种子集和问题。
递归函数应该提供:
stop condition:
when sum is zero and left count is zero - success
when sum is zero and left count is non-zero - fail
when sum is negative - fail
traverse possible variants to solve simpler problem at the next recursion level:
for every stamp value v check -
is it possible to make solution using value v and result of recursive call for count n-1
(note: to avoid duplicate solutions, start traversal from the same stamp index, omitting lower indexes)
关于java - 一种递归求解邮票问题的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55486337/