165 - Stamps

[ehaque]

Is there anyone who can give me some inputs to problem 165 ( STAMPS) ?

Tamim

[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,

[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.

[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.

[junbin]

Use a mixture of DP and BFS.

[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....

[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.

[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"?

[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?

[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]

[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.