Dynami c программирование - ловить мяч - PullRequest
Новая
       5

Dynami c программирование - ловить мяч

0 голосов
/ 07 марта 2020

Я пытаюсь решить следующую проблему:

Шары падают с неба. Мы знаем, в каком месте (на прямой линии) будет падать каждый шар, и мы знаем время (в секундах), в которое мяч достигнет земли. Мы пытаемся поймать их в шар net, который мы можем перемещать влево или вправо, но каждое движение стоит 1 секунду. Начальная позиция бал lnet всегда слева (позиция 0). Нам разрешено> отбросить (не поймать) k кол-во шаров.

Какую максимальную оценку мы можем достичь?

Моя первая попытка решить эту проблему была жадным алгоритмом: 

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++

однако мой алгоритм не учитывает, что иногда лучше пожертвовать некоторым количеством шаров, чтобы достичь более высокого счета в долгосрочной перспективе. Это требует подхода с помощью динамического c программирования, я думаю.

Является ли эта проблема известной, и я могу найти какую-то помощь? Не могли бы вы помочь мне с этой проблемой? Я могу решить эту проблему жадным путем, но я не могу сделать это динамически.

Спасибо

1 Ответ

1 голос
/ 21 апреля 2020

За любой данный шар вы можете либо поймать его (если возможно), либо сбросить и потерять «жизнь». Чтобы решить, следует ли вам пожертвовать жизнью ради какого-либо данного шара, создайте дерево решений, в котором вы либо поймаете мяч, либо уроните его. Ваше дерево разветвляется, создавая 2 ^ n подзадач. На каждом уровне дерева у вас будет максимум k уникальных подзадач, поскольку вы достигнете этой точки от 1 до k жизней. Создайте матрицу с лучшим счетом, который вы можете получить за i-й мяч, оставив k жизней, если вы его поймаете. Затем вы можете ссылаться на эти значения, чтобы избежать лишней работы. Когда k и количество шаров невелики, вы можете использовать динамическое программирование c, чтобы исследовать все возможные комбинации уловов / падений за приемлемый промежуток времени.

...