1. Набираем команду codeby webinar. Набираем команду для организации и проведения вебинаров. Подробнее ...

    Скрыть объявление
  2. Требуются разработчики и тестеры для проекта codebyOS. Требования для участия в проекте: Знание принципов работы ОС на базе Linux; Знание Bash; Крайне желательное знание CPP, Python, Lua; Навыки системного администрирования. Подробнее ...

    Скрыть объявление
  3. Получи 30.000 рублей. Для получения денег необходимо принять участие в конкурсе авторов codeby. С условиями и призами можно ознакомиться на этой странице ...

    Внимание! Регистрация авторов на конкурс закрыта.

    Скрыть объявление

Доказательство жадного алгоритма для выбора заявок

Тема в разделе "Вопросы новичков и не только", создана пользователем BredoZavR, 13 янв 2010.

  1. BredoZavR

    BredoZavR Гость

    Репутация:
    0
    Задача о заявках (расширенная)
    Удовлетворить все заявки в наименьшее количество аудиторий.
    Алгоритм написан, реализован
    Состоит в том, что заявки сортируются не как при обычном Greedy Activity Selector по окончании, а по количеству совместных с ними (по возрастающей)

    Проблема в доказательстве
    Нужно доказать правильность работы алгоритма. Обосновать. Прошу помощи. Сама уже не справляюсь
    Первым шагом нужно доказать, что выбор заявок в первую аудиторию не закрывает путь к оптимальному решению... То есть, что аудитория, наполненная с помощью моего алгоритма, может присутствовать в оптимальном решении.

    Надо будет код, вставлю
     

Поделиться этой страницей