Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.12.2022, 06:30   #1
Шляпадляменя
Пользователь
 
Регистрация: 01.12.2022
Сообщений: 18
По умолчанию Поиск наибольшего подмножества множеств

Требуется реализовать алгоритм поиска наибольшего подмножества взаимно совместимых процессов (функция get_max_activities; каждый процесс характеризуется временным интервалом [start, finish), два процесса совместимы если их интервалы не пересекаются).
Реализовать алгоритм наивным способом: полный перебор всех возможных подмножеств множества процессов с выбором среди них подмножества взаимно совместимых процессов максимального размера.

Я написал алгоритм, но мне сказали, что это не полный перебор. Помоги переделать
Код:
bool ret(const Activity& a, const Activity& b)
{
    if (a.finish < b.finish)
        return true;
    else return false;

}

std::vector<Activity> get_max_activities(const std::vector<Activity>& activities) {
    vector<Activity> rezult,v,m=activities;
    int k;
    sort(m.begin(), m.end(), ret);
    if (m.size() == 0)
        return m;
    rezult.push_back(m[0]);
   
    for (int i = 0; i < m.size(); i++) {
        v.clear();
        k = 1;
        v.push_back(m[i]);
        for (int j = i + 1; j < m.size(); j++)
            if (m[j].start >= v[k - 1].finish) {
                v.push_back(m[j]);
                k++;
            }
        if (v.size() > rezult.size())
            rezult = v;
    }
    return rezult;
}
Шляпадляменя вне форума Ответить с цитированием
Старый 10.12.2022, 17:10   #2
Шляпадляменя
Пользователь
 
Регистрация: 01.12.2022
Сообщений: 18
По умолчанию

Если нужен полный код
Код:
class Activity {
public:
    Activity() = default;
    Activity(int start, int finish) :
        start(start), finish(finish) {
    }

    bool operator<(const Activity& a) const;
    bool operator==(const Activity& a) const;

public:
    int start{ 0 };
    int finish{ 0 };
};
Например у меня есть множество { {2, 6}, {1, 4}, {7, 10}, {5, 8} }
Наименьшее подмножества множества будет { {1, 4}, {5, 8} }, т.к конечное число(4) меньше первого числа следующего множества(5)

Последний раз редактировалось Шляпадляменя; 11.12.2022 в 09:59.
Шляпадляменя вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
На плоскости N различных точек заданы своими координатами. Найти уравнение прямой, делящей это множество точек на 2 равномощных подмножества (т.е. на подмножества с одинаковым коли scarecrow_1 Python 1 28.02.2017 09:53
Из множества конечных множеств выделить подмножество из наибольшего количества попарно непересекающихся множеств(Maple или Паскаль Моника Помощь студентам 0 28.04.2014 23:18
C + Assembler: Поиск наибольшего числа в массиве Arnezami Помощь студентам 1 05.02.2012 10:10
Поиск наибольшего значения (Delphi) Сварог Помощь студентам 1 05.11.2011 11:51
Поиск подмножества Lodyr Общие вопросы C/C++ 15 27.11.2010 21:38