Bob*_*y S 9 algorithm combinatorics discrete-mathematics
邮票问题是一个数学问题,询问如果信件只能容纳有限数量的邮票,那么不能放在信封上的最小邮资价值是多少,而这些邮票可能只有某些指定的面值.
例如,假设信封只能容纳三个邮票,可用的邮票价值分别为1美分,2美分,5美分和20美分.然后解决方案是13美分; 因为任何较小的值都可以获得最多三个邮票(例如4 = 2 + 2,8 = 5 + 2 + 1等),但要获得13美分,必须使用至少四个邮票.
是否有算法给出允许的最大邮票数量和邮票的面值,人们可以找到不能放在信封上的最小邮资？
另一个例子:
最多可以使用5个标记
值:
1,4,12,21无法达到的最小值是72.可以使用特定组合创建值1-71.
最后我可能会使用Java来编写代码.
是的，有这样的算法。天真地：从 1 开始，尝试所有可能的邮票组合，直到找到总和为 1 的组合，然后尝试 2，依此类推。当您的算法找到一个数字并且没有任何邮票组合可以添加到该数字时，您的算法就完成了。
尽管可能很慢，但对于足够小的问题（例如 100 个邮票，10 个位置），您可以在“合理”的时间内解决这个问题......
但是，对于大型问题，即我们有许多可用标记（例如 1000 个）和许多可能的位置（例如 1000 个）的问题，该算法可能会花费大量时间。也就是说，对于非常大的问题，使用这种方法解决问题的时间可能是宇宙的寿命，因此它对您来说并不是真正有用。
如果您有非常大的问题，您需要找到加快搜索速度的方法，这些加速称为启发式。你无法解决问题，但通过应用某种领域知识，你可能可以比简单的方法更快地解决问题。
改进这种天真的方法的一个简单方法可能是，每当您尝试不等于您要查找的数字的邮票组合时，您都会从可能的集合中删除该组合以尝试任何未来的数字，并标记该未来号码为不可用。换句话说：保留一个你已经找到的数字和组合的列表，然后不要再次寻找这些数字或它们的组合。