# Catching ball - finding the maximum number of caught balls

I'm attempting to solve the following problem:

Balls are falling from the sky. We know at which location (on a straight line) will each ball drop, and we know the time (in seconds) at which will the ball reach the ground. We are trying to catch them into a ball net, which we can move left or right, but each movement costs 1 second. The initial position of a ballnet is always on the left (position 0). We are allowed to > drop (not catch) $$k$$ number of balls.

What is the highest score we can achieve?

My first attempt at solving this was a greedy algorithm:

if the |next ball position - current position of the ball net| > (time of the next ball - current time)
then attempts++
if attempts>$$k$$
print game over
else
current ball net position = next ball position
current time = time of the next ball
score++


however my algorithm doesn't take into consideration that sometimes it's better to sacrifice some number of balls in order to reach a higher score in the long run. This needs an approach via dynamic programming, I think.

Is this problem a known one so I can find some help? Could you help me with this problem? I can solve this in a greedy way, however I am failing to do it dynamically.

Thanks!

• This looks like a competition or homework problem. Could you provide a link to the competition, so we know it's no longer active? Thanks. – j_random_hacker Mar 7 at 20:57
• @j_random_hacker it's not a competition, it's a problem from my advanced algorithms class. – Daniel Mar 7 at 22:00
• OK, hint: See if you can compute the largest number of balls that you can catch given that you are at position $i$ a few milliseconds before time $t$. – j_random_hacker Mar 7 at 22:04
• Try dynamic progtramming. – vonbrand Mar 7 at 22:25
• cs.stackexchange.com/tags/dynamic-programming/info – D.W. Mar 8 at 5:08