(Динамическое программирование) Как максимально использовать комнату с помощью списка встреч?

Я не уверен, как вы связываете это с проблемой рюкзака. Мне кажется, что это больше проблема вершинного покрытия.

Сначала отсортируйте интервалы по времени их начала и сформируйте графическое представление в виде матрицы смежности или списка.

Вершины должны быть номерами интервалов. Между двумя вершинами должно быть ребро, если соответствующие интервалы пересекаются друг с другом. Кроме того, каждой вершине должно быть присвоено значение, равное длительности интервала.

Тогда возникает проблема выбора независимых вершин таким образом, чтобы общее значение было максимальным.

Это можно сделать с помощью динамического программирования. Рекуррентное соотношение для каждой вершины должно быть следующим:

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 не может быть никакого ребра.

Хороший подход состоит в том, чтобы создать класс, который может легко справиться за вас.

Сначала я создаю вспомогательный класс для удобного хранения интервалов.

public class FromToDateTime
{
    private DateTime _start;
    public DateTime Start
    {
        get
        {
            return _start;
        }
        set
        {
            _start = value;
        }
    }

    private DateTime _end;
    public DateTime End
    {
        get
        {
            return _end;
        }
        set
        {
            _end = value;
        }
    }

    public FromToDateTime(DateTime start, DateTime end)
    {
        Start = start;
        End = end;
    }
}

А вот еще класс Room, в котором есть все интервалы и у которого есть метод addInterval, который возвращает true, если интервал в порядке и был добавлен, и false, если нет.

Кстати: у меня есть условие проверки для перекрытия здесь: Алгоритм обнаружения перекрывающихся периодов

public class Room
{
    private List<FromToDateTime> _intervals;
    public List<FromToDateTime> Intervals
    {
        get
        {
            return _intervals;
        }
        set
        {
            _intervals = value;
        }
    }

    public Room()
    {
        Intervals = new List<FromToDateTime>();
    }

    public bool addInterval(FromToDateTime newInterval)
    {
        foreach (FromToDateTime interval in Intervals)
        {
            if (newInterval.Start < interval.End && interval.Start < newInterval.End)
            {
                return false;
            }
        }
        Intervals.Add(newInterval);
        return true;
    }
}

В то время как более общая проблема (если у вас несколько конференц-залов) действительно является NP-Hard и известна как проблема интервального планирования.

Оптимальное решение одномерной задачи с одним классом:
Для одномерной задачи выбор (все еще допустимого) самого раннего крайнего срока сначала решает проблему оптимально.

Доказательство: по индукции базовое предложение является недействительным — алгоритм оптимально решает проблему с нулевым числом встреч.

Гипотеза индукции состоит в том, что алгоритм решает задачу оптимально для любого количества k задач.

Шаг: при наличии проблемы с n собраниями установите самый ранний крайний срок и удалите все недействительные собрания после его выбора. Пусть выбранная задача с самым ранним сроком будет T.
Вы получите новую задачу меньшего размера, а задействовав алгоритм на напоминании, получите для них оптимальное решение (гипотеза индукции).
Теперь обратите внимание, что при таком оптимальном решении вы можете добавить максимум одну из отброшенных задач, поскольку вы можете либо добавить T, либо другую отброшенную задачу, но все они перекрываются с T, иначе они не были бы отброшены. ), таким образом, вы можете добавить максимум одну из всех отброшенных задач, как и в предложенном алгоритме.

Вывод: Для 1 переговорной данный алгоритм оптимален.

КЭД

высокоуровневый псевдокод решения:

findOptimal(list<tasks>):
   res = [] //empty list
   sort(list) //according to deadline/meeting end
   while (list.IsEmpty() == false):
        res = res.append(list.first())
        end = list.first().endTime()
        //remove all overlaps with the chosen meeting
        while (list.first().startTine() < end):
              list.removeFirst()
   return res

Пояснение. В этом ответе предполагается, что использование помещения означает максимальное количество совещаний, проводимых в помещении.

Всем спасибо, вот мое решение, основанное на этом Принстоне. примечание о динамическом программировании.

Алгоритм:

1. Отсортируйте все события по времени окончания.
2. Для каждого события найдите p[n] — самое позднее событие (по времени окончания), которое с ним не пересекается.

3. Вычислите значения оптимизации: выберите лучший вариант между включением/исключением события.

   Optimize(n) {
       opt(0) = 0;
       for j = 1 to n-th {
           opt(j) = max(length(j) + opt[p(j)], opt[j-1]);
       }               
   }
   

Полный исходный код:

    namespace CommonProblems.Algorithm.DynamicProgramming {
    public class Scheduler {
        #region init & test
        public List<Event> _events { get; set; }

        public List<Event> Init() {
            if (_events == null) {
                _events = new List<Event>();
                _events.Add(new Event(8, 11));
                _events.Add(new Event(6, 10));
                _events.Add(new Event(5, 9));
                _events.Add(new Event(3, 8));
                _events.Add(new Event(4, 7));
                _events.Add(new Event(0, 6));
                _events.Add(new Event(3, 5));
                _events.Add(new Event(1, 4));
            }

            return _events;
        }

        public void DemoOptimize() {
            this.Init();
            this.DynamicOptimize(this._events);
        }
        #endregion

        #region Dynamic Programming
        public void DynamicOptimize(List<Event> events) {
            events.Add(new Event(0, 0));
            events = events.SortByEndTime();

            int[] eventIndexes = getCompatibleEvent(events);
            int[] utilization = getBestUtilization(events, eventIndexes);
            List<Event> schedule = getOptimizeSchedule(events, events.Count - 1, utilization, eventIndexes);

            foreach (var e in schedule) {
                Console.WriteLine("Event: [{0}- {1}]", e.Start, e.End);
            }
        }

        /*
        Algo to get optimization value:
        1) Sort all events by end time, give each of the an index.
        2) For each event, find p[n] - the latest event (by end time) which does not overlap with it.
        3) Compute the optimization values: choose the best between including/not including the event.

        Optimize(n) {
            opt(0) = 0;
            for j = 1 to n-th {
                opt(j) = max(length(j) + opt[p(j)], opt[j-1]);
            }
            display opt();
        }
        */
        int[] getBestUtilization(List<Event> sortedEvents, int[] compatibleEvents) {
            int[] optimal = new int[sortedEvents.Count];
            int n = optimal.Length;

            optimal[0] = 0;

            for (int j = 1; j < n; j++) {
                var thisEvent = sortedEvents[j];

                //pick between 2 choices:
                optimal[j] = Math.Max(thisEvent.Duration + optimal[compatibleEvents[j]],  //Include this event
                                       optimal[j - 1]);                                   //Not include
            }

            return optimal;
        }

        /* 
        Show the optimized events: 
            sortedEvents: events sorted by end time.
            index: event index to start with.
            optimal: optimal[n] = the optimized schedule at n-th event.
            compatibleEvents: compatibleEvents[n] = the latest event before n-th
         */
        List<Event> getOptimizeSchedule(List<Event> sortedEvents, int index, int[] optimal, int[] compatibleEvents) {
            List<Event> output = new List<Event>();
            if (index == 0) {
                //base case: no more event
                return output;
            }

            //it's better to choose this event
            else if (sortedEvents[index].Duration + optimal[compatibleEvents[index]] >= optimal[index]) {
                output.Add(sortedEvents[index]);

                //recursive go back
                output.AddRange(getOptimizeSchedule(sortedEvents, compatibleEvents[index], optimal, compatibleEvents));
                return output;
            }

            //it's better NOT choose this event
            else {
                output.AddRange(getOptimizeSchedule(sortedEvents, index - 1, optimal, compatibleEvents));
                return output;
            }
        }

        //compatibleEvents[n] = the latest event which do not overlap with n-th.
        int[] getCompatibleEvent(List<Event> sortedEvents) {
            int[] compatibleEvents = new int[sortedEvents.Count];

            for (int i = 0; i < sortedEvents.Count; i++) {
                for (int j = 0; j <= i; j++) {
                    if (!sortedEvents[j].IsOverlap(sortedEvents[i])) {
                        compatibleEvents[i] = j;
                    }
                }
            }
            return compatibleEvents;
        }
        #endregion
    }
    public class Event {
        public int EventId { get; set; }
        public bool IsOverlap(Event other) {
            return !(this.End <= other.Start ||
                    this.Start >= other.End);
        }
        public override bool Equals(object obj) {
            var i = (Event)obj;
            return base.Equals(obj) && i.Start == this.Start && i.End == this.End;
        }
        public int Start { get; set; }
        public int End { get; set; }
        public Event(int start, int end) {
            Start = start;
            End = end;
        }
        public int Duration {
            get {
                return End - Start;
            }
        }
    }
    public static class ListExtension {
        public static bool ContainsOverlapped(this List<Event> 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 static List<Event> SortByEndTime(this List<Event> events) {
            if (events == null) return new List<Event>();

            return events.OrderBy(x => x.End).ToList();
        }
    }
}