Question 1 There's a Hole in the Bucket

Waterloo Local Contest Dynamic Programming

You are likely familiar with the story of Henry an Liza and the hole in the bucket. Not too many people know what happened after Henry managed to fix the hole in his bucket. Liza, after the hole affair, was pretty upset with Henry. In an effort to get him to think, she had him fill a barrel with several different buckets. The barrel had to be filled exactly to the top by whole (or is that hole?) bucket quantities. Henry, being lazy, kept thinking about it until he could do it in the fewest buckets possible.

The Input:

The input will be a series of lines. The first line will contain a single number representing the size of the barrel in litres. The second and following lines each contain a single number representing the sizes of the available buckets, in litres.

The Output:

The output will be a single number representing the fewest buckets it takes to fill the barrel. 
Sample Input A:		Sample Input B:		Sample Input C:
17			20			36
1			7			19
2			5			9
4			3			5
5			1			2
						1

Sample Output A:	Sample Output B:	Sample Output C:
4			4			4

Limits:

The barrel will never be greater than 40 litres. The pails will never be larger than the barrel, nor will there be more than 10 pails.

Solution (Yogy Namara) :

Obviously, the dynamic programming solution is to keep a record of the fewest steps required to fill the barrel to each of the quantities within the range. Let N be the quantity of the barrel, and Best be an array [0..40] of Byte. Best[i] is the fewest steps required to fill the barrel to quantity i.

We start with Best[0]=0, and no explanation is needed for that . The initial values of Best[i], where i=1..N, are maximum values, and we will minimize them later.

Let j be the size of the current bucket we are using. Suppose that we have managed to fill the barrel to the quantity of i in Best[i] steps, and it's the fewest steps possible at that moment. Then with the current bucket, we need one extra step to fill the barrel to the quantity of i+j. And of course, we will only consider the values where i+j<=N (i.e. i=0..N-j), and where Best[i]+1<Best[i+j].

yogy-n@sby.mega.net.id GeoCities