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

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

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 13.05.2019, 17:10   #1
Константин01
Пользователь
 
Регистрация: 11.05.2019
Сообщений: 21
По умолчанию Максимальное независимое множество

Здравствуйте!

Необходимо написать реализацию алгоритма динамического программирования для поиска максимального независимого множества.

Я использую рекурсивную формулу, которая берет максимум из m1 и m2, где m1 - сумма (корень + внуки и внуки внуков), а m2 - сумма (дети и дети детей).

Я пишу рекурсивную функцию для поиска m1, однако функция не работает - возвращает сумму корня + первого внука. Прошу посмотреть в чем ошибка рекурсии. По возможности предложить более рациональное решение задачи.

Код:
int maxIS(int v, Graph G)
{
    vector<int> adj1 = {0}; // для записи первого списка смежности(дети)
    vector<int> adj2 = {0}; // для записи второго списка смежности(внуки)
    int m1; 
    int m2;
 
    int val[10] = {0};
 
    if (G.isLeaf(v))
    
    {
        val[v] = G.getWeight(v);
    }
 
    else
    {
        m1 = G.getWeight(v); // возвращает вес вершины
        adj1 = G.getConnections(v); // возвращает вектор с потомками (дети)
        for (size_t i=0; i<adj1.size(); i++)
        {
            adj2 = G.getConnections(adj1[i]); // возвращает вектор с потомками (внуки)
            for (size_t j=0; j<adj2.size(); j++)
            {
                m1 = m1 + maxIS(adj2[j], G);
            }
        }
          return m1;    
}
  
}


В данном коде массив val[10] и значение m2 игнорировать. Интересует лишь значение m1
Константин01 вне форума Ответить с цитированием
Старый 13.05.2019, 18:06   #2
taras-proger77
Заблокирован
 
Регистрация: 17.12.2018
Сообщений: 514
По умолчанию

Цитата:
Сообщение от Константин01 Посмотреть сообщение
Я использую рекурсивную формулу, которая берет максимум из m1 и m2, где m1 - сумма (корень + внуки и внуки внуков), а m2 - сумма (дети и дети детей).
С чем связана такая чётность уровней учитывамых узлов?
taras-proger77 вне форума Ответить с цитированием
Ответ


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

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Программа в Паскале: Даны три множества : Х1, Х2, Х3. Сформировать множество Y=(X1UX2) ⋂(X1UX3)\(X2UX3) и множество Y1 Агнесска Помощь студентам 0 06.05.2016 13:50
Требуется найти число способов выбрать из набора интервалов максимальное множество непресекающихся интревалов Filia Помощь студентам 0 06.10.2011 20:45
Множество, содержащее натуральные числа из первой сотни. Сформировать новое множество из простых чисел первого множества Aimet Паскаль, Turbo Pascal, PascalABC.NET 3 16.06.2011 20:50
Найти максимальное независимое множество вершин графа ebozzzavrik Помощь студентам 4 18.05.2011 23:21
Дано множество А, напечатать четные элементы, входящие в другое множество (Паскаль) Марийка92 Помощь студентам 4 03.04.2011 17:38