this can be solved in a manner similar to knapsack problem.
u can take the weight of tha knapsack the be the the various amounts u need
to make, 13 cents etc etc. we would need to find a first empty cell.
instead of parameter "value", use your own parameter specifying the number
of stamps used.
and u would have to make a smal intuitive change to the manner in which the
cells are populated so as to ensure that it picks a combination which
reaches an exact amount/weight that u need as opposed to a <= amount/weight
in regular knapsack.
On Tue, Jun 19, 2012 at 10:41 PM, rammar <getam...@gmail.com> wrote:
> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Aditya Gupta
B.Tech III yr CSE
IITR
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
