dynamic programming to find the minimum weight cover of the points

You are given n points p1, p2, . . . , pn on the real line. The location of pi is given by its coordinate xi . You are also given m intervals I1, I2, . . . , Im where Ij = [aj , bj ] (aj is the left end point and bj is the right end point). Each interval j has a non-negative weight wj . An interval Ij is said to cover pi if xi ∈ [aj , bj ]. A subset S ⊆ {I1, I2, . . . , Im} of intervals is a cover for the given points if for each pi , 1 ≤ i ≤ n, there is some interval in S that covers pi . In the figure below, the intervals shown in bold form a cover of the points.

The goal is to find a minimum weight cover of the points. Note that a minimum weight cover may differ from a cover with minimum number of intervals.

ps: I first tried to find the smallest interval, each time we find a valid smallest interval we remove its covered points from P[ ] until P[ ] is empty, but this algorithms can be easily prove to be wrong. Then I tried to pick the minimum ratio of weight to number of its covering points, but I do not know how to apply it into dp with memoization.

Answers


So what we can do here is first sort all the p[] array values and also sort the intervals according to a[] i.e the left end point.

Now at each state we can have two index, the first is the index of the interval and the second is the index of the point

So at each state what we have two cases:

The first case is simple, i.e we do not select the current interval.

In the second case what we can do is select the current interval if the point lies inside, also note that if we take the current interval than we can just move the index of the point in the new state forward by the no of points we find in the current interval since they are sorted.

Pseudo code for Recursive Dynamic Programming solution using memoisation:

#define INF 1e9

int n = 100;
int m = 100;

int p[100], a[100], b[100], w[100], memo[100][100];//initialize memo to -1

int solve(int intervalIndex, int pointIndex){

    if(intervalIndex == m){
        if(pointIndex == n) return 0;
        else return INF;
    }
    if(pointIndex == n) return 0;
    if(memo[intervalIndex][pointIndex] != -1) return memo[intervalIndex][pointIndex];

    //we can make 2 choices either to select this interval ao not to select this interval
    //if we select this interval, then we also take the points that it covers

    //case #1 : do not take current interval
    int ans = solve(intervalIndex + 1, pointIndex);

    if(a[intervalIndex] <= p[pointIndex] && b[intervalIndex] >= p[pointIndex]){     //i.e this point is inside curr interval
        //case # 2 : take current interval, and all the points it contains
        int index = pointIndex;
        for(int i = pointIndex + 1; i < n; i++){
            if(a[intervalIndex] <= p[i] && b[i] >= p[i]){
                index = i;
            }else{
                break;
            }
        }
        ans = min(ans, solve(intervalIndex + 1, index + 1) + w[intervalIndex]);
    }

    return memo[intervalIndex][pointIndex] = ans;
}

The above can be modified for real numbers easily.

The complexity of above code is O(m*n*n), but it can be reduced to O(m * n), if we just precompute the value that what is the farthest point index corresponding to an interval, so that we do not have to use the for loop inside to search for it, instead just use the precomputed value.


Need Your Help

Can I Do a Foreach on a TimeSpan by Timespan Type?

vb.net foreach timespan

I have a requirement that regardless of the start and dates that I need to loop through that timespan and calculate figures at the month level. I cannot seem to figure it out, and maybe it is not

Slice pandas DataFrame where column's value exists in another array

python numpy pandas

I have a pandas.DataFrame with a large amount of data. In one column are randomly repeating keys. In another array I have a list of of theys keys for which I would like to slice from the DataFrame ...