Re: [algogeeks] Re: POSTAGE STAMP PROBLEM
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.
[algogeeks] Re: POSTAGE STAMP PROBLEM
isnt it is similar to coin change problem , here we need minimum number of stamps to form a value. so we can check which number exceed the min stamp range i.e 1 to 3. On Jun 19, 11:55 am, sanjay pandey sanjaypandey...@gmail.com 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 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.
Re: [algogeeks] Re: POSTAGE STAMP PROBLEM
@atul if range is high den complexity wud be much larger... -- 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.
[algogeeks] Re: POSTAGE STAMP PROBLEM
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.
Re: [algogeeks] Re: POSTAGE STAMP PROBLEM
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.
