Я хотел бы написать алгоритм динамического программирования, который решает следующую проблему; для этого я хотел бы определить правильное отношение повторения. Это постановка проблемы:
Рассмотрим прямую дорогу длиной K миль, на которой мы стремимся разместить телефонные антенны. Доступные сайты характеризуются целыми числами x1, x2 ,. , , , xn, где xi представляет положение антенн вдоль дороги в милях (0 ≤ xi ≤ K). Кроме того, антенна, расположенная в положении xi, генерирует доход r (0 ≤ i ≤ n). Расстояние между двумя последовательными антеннами не может быть меньше или равно 5 километрам. Как и где вы должны разместить свои антенны, чтобы максимизировать свой доход.
Вот рекуррентное соотношение, которое я написал:
переменные параметры:
k: длина дороги
XI: положение антенны
xi-x (i +1)> 5
Это для максимального увеличения количества размещаемых антенн. Таким образом, пусть N будет количеством размещаемых антенн. Тогда N зависит от k и xi.
Во-первых, если первая антенна находится в положении xi, то есть k километров, на которые можно разместить антенны. Антенна будет размещена рядом с позицией 5 + xi, тогда она останется k-5-километровым xi, на котором можно разместить антенны.
Если я решу не устанавливать антенну в положении xi, я могу установить их в положении 5 + xi.
Отсюда мое следующее рекуррентное соотношение:
N (k, i) = max (Nxi, k) + N5 + xi, N (xi, in) & & N (xi, in)
Это правильно? Спасибо.
Это мой алгоритм (я хочу алгоритм в O (n) ):
Algorithm Antenna(\emph{int K, int xi, int profit)
{
int K: road lenght
int xi: position of antenna i
While{j < k}
{
xi = j
if{xi < k}
{
return idealPosition
}
j = j+5
return profit
}
}
О прибыли: чем больше у вас антенны, тем больше вы прибыли.