Page 1 of 1
Problem 165 ... help neeedeeeeddddddddddddd!!!!!!!!!!!!!!
Posted: Sat Aug 09, 2003 8:21 am
by ehaque
Is there anyone who can give me some inputs to problem 165 ( STAMPS) ?
Tamim
Posted: Thu Oct 16, 2003 8:52 am
by Whinii F.
Can anybody who got AC post their output with this input?
It seems like an easy problem but I'm stuck on this
5 4
4 5
6 3
8 2
4 4
5 5
0 0
Thanks in advance,
Posted: Thu Oct 16, 2003 12:33 pm
by junjieliang
My AC program's output:
Code: Select all
1 4 12 21 -> 71
1 3 11 15 32 -> 70
1 7 12 -> 52
1 5 -> 28
1 3 11 18 -> 44
1 4 9 31 51 -> 126
Hope this helps.
165 - Stamps
Posted: Tue Dec 16, 2003 9:48 am
by redglim
I just calculate all the cases (BF..) and got AC,
but i think that is not a good idea
plz give me some hint of more efficient (more fast)
method to solve this problem.
Posted: Tue Dec 16, 2003 7:57 pm
by junbin
Use a mixture of DP and BFS.
Posted: Wed Dec 17, 2003 5:03 am
by redglim
Thanks.
But unfortunately,
I cant find how to use DP for this problem.. (Im a beginner
)
Could you explain me how to use it..?
my algorithm is like this:
input:
3 3
0 0
1) First, find all the possible set of stamps. (by recursive function)
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 3 4
...
...
1 4 6
1 4 7
1 4 8
2) if a set can make some values, save it in an array.
ex) 1 2 3
0*1 + 0*2 + 0*3 = 0 result[0] = 1;
1*1 + 0*2 + 0*3 = 1 result[1] = 1;
2*1 + 0*2 + 0*3 = 2 result[2] = 1;
3*1 + 0*2 + 0*3 = 3 result[3] = 1;
0*1 + 1*2 + 0*3 = 2 result[2] = 1;
1*1 + 1*2 + 0*3 = 3 result[3] = 1;
2*1 + 1*2 + 0*3 = 4 result[4] = 1;
...
...
3) find the largest attainable value in a continuous sequence:
for (i=0;i<MAX;i++)
{
if (result == 0) {maxvalue = i-1;break;}
}
4) do '2)' and '3)' to all the set of stamps, and
find a set which has the biggest 'maxvalue'
Please give me some help~.
I cant find more efficient way....
Posted: Wed Dec 17, 2003 6:04 am
by junbin
After you use BFS to generate a list of possible stamps, you can use DP to check if those stamps can be used to fit a certain value and the mininum number of stamps required. If this mininum is less than or equal to h, then it's fine.
Using the DP table, you can thus determine easily and quickly the biggest value you can make with the limitations.
Another speed up is the fact that the DP table can be modified such that all of them share common points.. so you only need to modify parts of it each time.
Posted: Mon Apr 25, 2005 1:57 am
by Abednego
How do you know you only need to go up to "1 4 8" when the input is 3 3? Why is it not '1 4 13"?
Posted: Fri Aug 19, 2005 11:32 am
by Mohammad Mahmudur Rahman
How can you use BFS to generate the list of stamps? I can do it using backtrackin but then, how can I determine the upper limit for values of the denominations?
Is precalc the only way?
Posted: Sat Apr 29, 2006 10:47 am
by serur
Hello Fellows!
to Mohammad Mahmudur Rahman-
I think the upper limit for denominators is n(h,k) for k stamps that you already found +1: here it is in my code, which gives TLE...
What do you think?
/[codespoiler }[/code]
Posted: Sat Apr 29, 2006 11:07 am
by serur
I am really consumed with shame - but I precalculated using this code and stored the whole array in my code and got AC.
Well, I see I am not alone.