This is a problem from another contest.

You have a set of N(1<=N<=32) clubs, each of which can hit the ball a
given length. You are also given a certain distance (1<=d<=5280). You
must find the minimal combination of clubs in order to get to that
distance, but you CANNOT go past the distance.

Anyway, I tried just cycling through the data and keeping track of
the minimum # of clubs it takes to get to a certain distance, so that
it doesn't keep longer if it took more to reach that distance on
another iteration; this is too slow for n=32. I also tried another
approach in which I sorted the clubs by the distance each hit the
ball, and then started out by finding the maximum number of times
that the biggest clubs goes into the distance, then the second
biggest, and so on. Still too slow.

Any suggestions? sorry if this is a newbie question...

I'm not sure this is the right place to post this question. Does
anybody know any other forums where I can post these types of
questions?

Thanks in advance

If I have understood the statement properly you are given n < 32
numbers and you want to find a subset of these numbers that add up to
d (1 < d < 5000) (and you can repeat them)

The problem is has a standard solution using dynamic programming;
if a[1], a[2], ..., a[n] are the numbers;
z(d) = min (z(d-a[i]) + 1) for every i = 1, 2, ..., n if z(d-a[i]) is
reachable;
z(0) is reachable with 0 numbers
you can calculate the array z using a recursive procedure, but
storing the results (not to calculate z(i) more than once)

and that's all;

Good luck.

Thanks!

Works perfect.

I was wondering if you know of any websites/books that have these
types of standard solutions and typical algorithms. I read Algorithms
in C, but it was much too general. Do you know of any websites/books
that are more specific, like the algorithm you gave?

I think there you can start from the VERY beginning, problems and
theory combined, really a wonderful place.

I think there you can start from the VERY beginning, problems and
theory combined, really a wonderful place.

The URL is
ace.delos.com/usacogate
to register or login

Well, I think it's too complicated for such things........ it's not
written for beginners..... you must have solved problems and
programmed for some time to understand this book...