邮票问题是一个数学难题,询问字母是否只能容纳有限数量的邮票,并且这些邮票只能具有某些特定的面值,因此最小的邮票价值不能放在信封上。
例如,假设信封只能容纳三个邮票,并且可用邮票价值分别为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个)的问题,此算法可能会花费很长的时间。也就是说,对于非常大的问题,使用这种方法解决问题的时间可能是宇宙的生命周期,因此对您而言并没有太大用处。
如果您确实有很大的问题,则需要找到加速搜索的方法,这些加速称为启发式。您无法解决问题,但是通过应用某种领域知识,可以比单纯的方法更快地解决问题。
改善这种幼稚方法的一种简单方法可能是,只要您尝试的邮票组合与您要查找的数字不相等,就从可能的组合中删除该组合以尝试任何未来的数字,并标记该未来号码不可用。换一种说法:保留您已经找到的数字列表以及将您带到那里的组合,然后不再寻找这些数字或它们的组合。