具有较小权重和的较大子集（"inverse" 加权间隔调度概率。）

Question

我想找到 WIS 问题的变体，其中结果必须是具有最小权重和的较大子集。例如，在：

    Input: Number of Intervals n = 5
            Interval Details: (start-finish, weight)
            Interval 1:  (0-5, 15) 
            Interval 2:  (4-9, 18)
            Interval 3:  (10-15, 12)
            Interval 4:  (8-21, 19)
            Interval 5:  (25-30, 25)

答案必须是子集 {3, 1, 5} 因为这是最大元素和最小权重和 ws = 52 ( 12 + 15 + 25) 的子集。

这个问题是一个项目的一部分，我为此在谷歌上搜索了很多，但以这种方式找到了任何东西。我不熟悉算法和编程，如果我在这里写了一些愚蠢的东西，我很抱歉。

你知道如何解决这个问题吗？

Answer 1

蛮力法：找到所有可能的开始间隔和所有可能的最后间隔，并计算开始和结束间隔之间的所有可能序列。这等于计算有向无环图 (DAG) 中节点对之间的所有路径。

计算起始间隔：

找出最短完成时间。
开始间隔是所有开始时间 < 最短结束时间的间隔。如果您从另一份工作开始，则需要省略一个间隔。

同样，计算结束间隔：

找到最大开始时间。
结束间隔是所有结束时间 > 最大开始时间的间隔。

计算这两组之间的所有路径：
这里您需要应用一种算法来计算 DAG 中的所有路径。实现可以在互联网上找到。一个例子：

void recursive(Interval current, Interval destination, List<Interval> path)
{
    path.Add(current);

    if (current == destination)
    { 
        if (path.Count > maxLength || (path.Count == maxLength && pathWeight < minWeight))
        {
            minWeightPath = new List<Interval>(path);
        }
        path.Remove(current);
        return;
    }

    //Successors are all intervals with startTime >= current.finishTime
    List<Interval> possibleSuccessors = getAllSuccessors();

    foreach (var item in possibleSuccessors)
    {
        recursive(item, destination, path);
    }

    path.Remove(current);
}

按以下方式调用此方法：

foreach (var startNode in startingNodes)
{
    List<Interval> path = new List<Interval>();
    foreach (var endNode in endNodes)
    {
        if (startNode.finishTime < endNode.startTime)
            recursive(startNode, endNode, path);
    }
}

具有较小权重和的较大子集（"inverse" 加权间隔调度概率。）

Larger subset with smaller weight sum ("inverse" Weighted Interval Scheduling Prob.)

algorithm

scheduling

intervals