c# - (动态规划)如何通过 session 列表最大化房间利用率？

Question

我正在尝试使用动态规划来解决这个问题

问题:

给定一个 session 室和一个间隔列表(代表 session )，例如:

• 间隔 1:1.00-2.00
• 间隔 2:2.00-4.00
• 间隔 3:14.00-16.00...等

问题:

如何安排 session 以最大限度地利用 session 室，并且 session 不应相互重叠？

尝试的解决方案

下面是我在 C# 中的初步尝试(知道这是一个修改后的带约束的背包问题)。但是我很难得到正确的结果。

bool ContainsOverlapped(List<Interval> list)
    {
        var sortedList = list.OrderBy(x => x.Start).ToList();
        for (int i = 0; i < sortedList.Count; i++)
        {
            for (int j = i + 1; j < sortedList.Count; j++)
            {
                if (sortedList[i].IsOverlap(sortedList[j]))
                    return true;
            }
        }
        return false;
    }
    public bool Optimize(List<Interval> intervals, int limit, List<Interval> itemSoFar){
        if (intervals == null || intervals.Count == 0)
            return true; //no more choice

        if (Sum(itemSoFar) > limit) //over limit
            return false;

        var arrInterval = intervals.ToArray();

        //try all choices
        for (int i = 0; i < arrInterval.Length; i++){
            List<Interval> remaining = new List<Interval>();
            for (int j = i + 1; j < arrInterval.Length; j++) { 
                remaining.Add(arrInterval[j]);
            }

            var partialChoice = new List<Interval>();
            partialChoice.AddRange(itemSoFar);
            partialChoice.Add(arrInterval[i]);

            //should not schedule overlap
            if (ContainsOverlapped(partialChoice))
                partialChoice.Remove(arrInterval[i]);

            if (Optimize(remaining, limit, partialChoice))
                return true;
            else
                partialChoice.Remove(arrInterval[i]); //undo
        }

        //try all solution
        return false;
    }


public class Interval
{
    public bool IsOverlap(Interval other)
    {
        return (other.Start < this.Start && this.Start < other.End) || //other < this
                (this.Start < other.Start && other.End < this.End) || // this covers other
                (other.Start < this.Start && this.End < other.End) || // other covers this
                (this.Start < other.Start && other.Start < this.End); //this < other
    }
    public override bool Equals(object obj){
        var i = (Interval)obj;
        return base.Equals(obj) && i.Start == this.Start && i.End == this.End;
    }
    public int Start { get; set; }
    public int End { get; set; }
    public Interval(int start, int end){
        Start = start;
        End = end;
    }
    public int Duration{
        get{
            return End - Start;
        }
    }
}

编辑1

房间利用率 = 房间被占用的时间。抱歉造成混淆。

编辑2

为简单起见:每个间隔的持续时间是整数，开始/结束时间从整点开始(1,2,3..24)

Answer 1

我不确定您是如何将此与背包问题联系起来的。在我看来，这更像是一个顶点覆盖问题。

首先按照开始时间对间隔进行排序，并以邻接矩阵或列表的形式形成图形表示。

顶点应为区间数。如果相应的区间相互重叠，则两个顶点之间应有一条边。此外，每个顶点都应关联一个等于间隔持续时间的值。

然后问题就变成了以总值最大的方式选择独立顶点。

这可以通过动态规划来完成。每个顶点的递归关系如下:

V[i] = max{ V[j]            | j < i and i->j is an edge, 
            V[k] + value[i] | k < i and there is no edge between i and k }

Base Case V[1] = value[1]

注意:
顶点应按开始时间的升序编号。那么如果有三个顶点:
i < j < k，如果顶点 i 和顶点 j 之间没有边，那么顶点 i 和顶点 k 之间也不可能有任何边。