求点最小权覆盖的动态规划

Question

给出n个点p1，p2，。。。，在真实的线路上。π的位置由它的坐标xi给出。也给出m间隔I1，I2，。。。，I= aj，bj。每个区间j都有一个非负权重wj .如果xi∈aj，bj，则称区间Ij覆盖π。子集S⊆{I1，I2，.。。区间的Im}是给定点的覆盖，如果对于每个π，1≤i≤n，S中有一个区间覆盖π。在图下面中，用粗体表示的间隔是对点的覆盖。

目标是找出点的最小重量覆盖。请注意，最小重量罩可能与间隔最小的盖子不同。

ps:我首先试图找到最小区间，每次我们找到一个有效的最小区间时，我们从P中删除它的覆盖点，直到P为空，但是这个算法很容易被证明是错误的。然后我试着选择最小权重与覆盖点数之比，但我不知道如何用回忆录把它应用到dp中。

Answer 1

所以我们可以做的是首先对所有的p[]数组值进行排序，并根据a[]对间隔进行排序，即左端点。

现在在每个状态下，我们可以有两个index，第一个是index of the interval，第二个是index of the point。

因此，在每个州，我们有两个案例：

第一种情况很简单，即我们不选择当前的间隔。

在第二种情况下，我们可以做的是选择当前区间，如果点位于内部，还请注意，如果我们采用当前间隔，则可以将新状态下的index of the point移动到当前区间中的no，因为它们是排序的。

使用Recursive Dynamic Programming解决方案使用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;
}

以上可以很容易地修改为实数。

上述代码的复杂性为O(m*n*n)，但可以简化为O(m * n)，只要预先计算与区间对应的最远点索引的值，就不必使用for循环来搜索它，而只需使用预先计算的值即可。