This can be done with DP.
Take an array with values 1 to n.
For every number i, try to make it using the stamps available and the 1 to
i-1 array. Anytime u find that the upper bound is reached, u return.
sudo code.
stamps[K]; -> Stamp denominations available.
a[N] -> Array of number of stamps required.
a[0] = 0;
For i= 1 to n
{
tempMin = 1000( some large number)
For j = 0 to K -> loop over the array storing the number of stamp
denominations.
{
if(stamps[j] <= i)
if( tempMin > 1 + a[i-j])
tempMin := 1 + a[i-j];
}
if(tempMin > maxStampAllowed)
{
return i;
}
else
{
a[i] =tempMin
}
}
This will work with time complexity of O (n*k) . Use of vectors (in c++)
can be helpfule for dynamic arrays.
P.S. Can we do better?
On Tuesday, June 19, 2012 9:25:42 PM UTC+5:30, suzi wrote:
>
> 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.
>
> 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?
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/a1ykZ8HaDjEJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
