Учитывая матрицу смежности, обозначающую стоимость между n элементами, как мне разделить n элементов на k групп?

Учитывая стоимость между n элементами, где cost[i][j] обозначает стоимость между элементами i и j, нам нужно разделить n элементов на k непустых групп так, чтобы, если 2 элемента принадлежат одной и той же группе, стоимость между пары становятся 0. Учитывая деление, пусть M будет минимальной стоимостью 2 пар, не принадлежащих к одной и той же группе. Мне нужно найти максимально возможное М. (деление нам не дано, нужно найти оптимальное деление, а затем найти максимально возможное М)

Я думал отсортировать все cost[i][j], а затем бинарный поиск по ним. Допустим, мы находимся в позиции x в отсортированном массиве, где стоимость равна M и обозначает ребро между (i,j). Мы предполагаем, что это максимально возможное M. Итак, мы знаем, что i-й и j-й элементы должны находиться в разных группах. Затем мы делаем bfs из i-го элемента и добавляем все соседние элементы со стоимостью меньше текущей M. Это будет в текущей группе. Мы продолжаем bfsing, пока у нас не закончатся элементы в этой группе. Затем мы переходим к нашей следующей группе и снова делаем bfs из j-го элемента. Если мы встречаем элемент, который уже находится в предыдущей группе, но имеет стоимость меньше, чем M, с элементом из текущей группы, мы либо возвращаем false, либо пытаемся объединить две группы. Это та часть, в которой я не уверен

например, если n = 3, k = 2 и стоимость [1] [2] = 17, стоимость [2] [3] = 15, стоимость [1] [3] = 16

мы можем поместить элемент 1 в группу 1 и элемент 2 в группы 2 и 3. Максимальное M в этом случае будет min(cost[1][2],cost[1][3]) = 16

Это лучшее, что можно сделать

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
0
58
1

Ответы 1

Если нет ограничения на минимальное количество элементов в группе или группы имеют одинаковое количество элементов, то лучше всего поместить все элементы, кроме элемента k-1, в одну группу, а все остальные группы состоят из одного элемента. Чтобы найти эти k-1 элементы, которые создают k-1 группы, отсортируйте стоимость по убыванию и возьмите первые k-1 появившиеся элементы.

Другие вопросы по теме