try this : similar problem
http://www.spoj.pl/problems/NOCHANGE/
On Tue, Jun 19, 2012 at 1:32 PM, aditya gupta <adityagupta...@gmail.com> wrote:
> 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.
--
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.
