This problem is called the postage stamp problem. Envision a country that issues

Question

This problem is called the postage stamp problem. Envision a country

that issues n different denominations of stamps but allows no more

than m stamps on a single letter. For given values of m and n, write

an algorithm that computes the greatest consecutive range of postage

values, from one on up, and all possible sets of denominations that

realize that range. For example, for n = 4 and m = 5, the stamps with

values (1, 4, 12, 21) allow the postage values 1 through 71. Are there

any other sets of four denominations that have the same range?

Explanation / Answer

First assume that you have a black box which calculates the range when given n, m and set of stamp values. Now iterate over all possible combinations of n-tuples. Let{a1; a2; :::; a4}, be the n-tuple. Start with {1;2; :::;4}. Vary ai from i till 71. Do this for each ai from a4 to a2.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.