邮票的信封上最大值 [英] Maximum value of postage stamps on an envelope

问题描述

邮票问题是询问什么是不能放置在信封的最小邮资值，如果信可以容纳邮票仅有限数量的数学谜语，并且这些可以仅具有某些特定面值。

The postage stamp problem is a mathematical riddle that asks what is the smallest postage value which cannot be placed on an envelope, if the letter can hold only a limited number of stamps, and these may only have certain specified face values.

例如，假设信封只能容纳三枚邮票，和现有的邮票值1美分，2美分，5美分，至20美分。然后将溶液是13美分;因为任何小的值可以用至多3邮票来获得（例如，4 = 2 + 2，8 = 5 + 2 + 1等），但要获得人们必须使用至少四个戳13美分。

For example, suppose the envelope can hold only three stamps, and the available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the solution is 13 cents; since any smaller value can be obtained with at most three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one must use at least four stamps.

有，鉴于邮票允许的最大数量和邮票面值的算法，可以找到最小的邮费，不能放置在信封上？

Is there an algorithm that given the maximum amount of stamps allowed and the face value of the stamps, one can find the smallest postage that cannot be placed on the envelope?

又如：
最多5个邮票可以使用
值：1，4，12，21
不能达到最小的值是72。值1-71可以与特定组合来创建。

Another example:
Maximum of 5 stamps can be used
Valued: 1, 4, 12, 21
The smallest value that cannot be reached is 72. Values 1-71 can be created with a certain combination.

在最后，我很可能会使用Java $ C C此$。

In the end I will probably be using Java to code this.

推荐答案

是的，有这样的算法。天真地：从1开始，尝试邮票每个可能的组合，直到我们发现，产生1之和的组合，然后尝试为2，等等。你的算法结束时，发现其数量，使得邮票没有组合增加了该号码。

Yes, there is such an algorithm. Naively: starting with 1, try every possible combination of stamps until we find a combination that yields a sum of 1, then try for 2, and so on. Your algorithm finishes when it finds a number such that no combination of stamps adds to that number.

虽然可能缓慢，足够小问题（比如100邮票，10个职位），你可以在一段合理数量解决这个...

Albeit possibly slow, for small enough problems (say 100 stamps, 10 positions) you can solve this in a "reasonable" amount of time...

不过，对于较大的问题，那些在那里我们有许多可用的邮票（比如1000）和许多可能的位置（比如1000），该算法可能需要的时间一个棘手的量。也就是说，对于非常大的问题时，及时使用这种方法可能会说，宇宙的寿命解决问题，因此它是不是真的对你有用。

But, for large problems, ones where we have many stamps available (say 1000s) and many possible positions (say 1000s), this algorithm might take an intractable amount of time. That is, for very large problems, the time to solve the problem using this approach might be say, the lifetime of the universe, and thus it's not really useful to you.

如果你有你需要找到办法，加快搜索速度真是大问题，这些加速比被称为启发式。你不能击败的问题，而是你都不可能解决问题，而不是天真的方法更快地运用某种​​领域的知识。

If you have really large problems you need to find ways to speed up your search, these speedups are called heuristics. You can't beat the problem, but you can possibly solve the problem faster than the naive approach by applying some sort of domain knowledge.

有一个简单的方法来改善这种幼稚的做法可能是，任何时候你试图邮票，这并不等于你找你的号码删除组合的组可能尝试为今后的任何数量的组合，和标志，未来数为不可用。另一种说法：要保持号码的列表，你已经发现，并且得到了你那里，然后不看那些数字或它们的组合再组合

A simple way to improve this naive approach might be that any time you try a combination of stamps that doesn't equal the number you're looking for you remove that combination from the possible set to try for any future number, and mark that future number as unavailable. Said another way: keep a list of numbers you've found already and the combinations that got you there, then don't look for those numbers or their combinations again.

这篇关于邮票的信封上最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！