Dynamic programming: recurrence relation

I would like to write a dynamic programming algorithm that solves the following problem; for that, I would like to define the proper recurrence relation. This is the statement of the problem: Consider a straight road with a length of K miles on which we seek to place phone antennas. Available sites are characterized by the integers x1, x2,. . . , xn where xi represents the position in miles, of an antennas along the road (0 ≤ xi ≤ K). In addition, an antenna placed at position xi generates a revenue of r (0 ≤ i ≤ n). The distance between two successive antennas cannot be less than or equal to 5 kilometers. How and where should you place your antennas to maximize your revenue.

Here's the recurrence relation that I wrote: variable parameters are: k: the length of the road xi: the position of the antenna xi-x (i +1)> 5

This is to maximize the number of antennas to be placed. Thus, let N be the number of antennas to be placed. Then N depends on k and xi. First, if the first antenna is placed at position xi, then there is k kilometer on which it is possible to place antennas. The antenna will be placed next to the position 5 + xi, then it will remain k-5-kilometers xi on which it is possible to place antennas. If I decide not to plant the antenna of the position xi, so I can p开发者_如何学Golant them in position 5 + xi.

Hence my following recurrence relation: N (k, i) = max (Nxi, k) + N5 + xi, N (xi, in) & & N (xi, in)

Is is correct? Thanks.

This is my algorithm (I want an algorithm 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
}
}

About the profit, the more you have antenna, the more you have profit.

Is it true that antennas can only be installed as specific sites?

I assume your sites are numbered sequentially. Starting from i=1, you can

(a) place an antenna at position i, the total score is 1 + your best score using only the remaining sites, i.e. all the sites j that are further than 5 miles from i (j>i) (b) not place an antenna at position i, and place it at i+1 instead. The total score is again 1 + whatever you can get using the remaining sites only.

The optimal solution is max(a,b)