小编典典

信封上的邮票最大值

algorithm

邮票问题是一个数学难题,询问字母是否只能容纳有限数量的邮票,并且这些邮票只能具有某些特定的面值,因此最小的邮票价值不能放在信封上。

例如,假设信封只能容纳三个邮票,并且可用邮票价值分别为1美分,2美分,5美分和20美分。那么解决方案是13美分;因为最多可以使用三个邮票获得较小的值(例如4
= 2 + 2,8 = 5 + 2 + 1等),但是要获得13美分,必须至少使用四个邮票。

是否有一种算法可以给定最大的邮票数量和邮票的面值,从而找到无法放在信封上的最小邮费?

另一个示例:
最多可以使用5个图章
值:
1、4、12、21不能达到的最小值是72。可以使用某种组合创建值1-71。

最后,我可能会使用Java对此进行编码。


阅读 330

收藏
2020-07-28

共1个答案

小编典典

是的,有这样的算法。天真的:从1开始,尝试所有可能的邮票组合,直到找到总和为1的组合,然后再尝试2,依此类推。当找到数字以致没有印记组合添加到该数字时,您的算法即告完成。

尽管可能很慢,但对于足够小的问题(例如100个邮票,10个位置),您可以在“合理的”时间内解决此问题…

但是,对于较大的问题,即那些有很多可用图章(例如1000个)和许多可能位置(例如1000个)的问题,此算法可能会花费很长的时间。也就是说,对于非常大的问题,使用这种方法解决问题的时间可能是宇宙的生命周期,因此对您而言并没有太大用处。

如果您确实有很大的问题,则需要找到加速搜索的方法,这些加速称为启发式。您无法解决问题,但是通过应用某种领域知识,可以比单纯的方法更快地解决问题。

改善这种幼稚方法的一种简单方法可能是,只要您尝试的邮票组合与您要查找的数字不相等,就从可能的组合中删除该组合以尝试任何未来的数字,并标记该未来号码不可用。换一种说法:保留您已经找到的数字列表以及将您带到那里的组合,然后不再寻找这些数字或它们的组合。

2020-07-28