powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачи о покрытии множества, нужна библиотека или функция
11 сообщений из 11, страница 1 из 1
Задачи о покрытии множества, нужна библиотека или функция
    #37051223
DelphiLexx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нужна библиотека (dll-файл) или модуль/функция (желательно на Delphi) для решения задачи о покрытии множества, суть которого:
1) Есть множество свойств {F}
2) Есть множество компонентов {K}
Каждый K обладает свойствами из множества {F}, а также каждому К соответствует один элемент P (вес), где P - это положительное число

Задача: Найти подмножество K, которое должно обладать подмножеством {F}, но при этом сумма Р полученных К должна быть минимальна.
Переводя на русский (хоть мы и программисты можем на разных балакать ), это звучало бы так:
Пример:
представим себе, что для выполнения какого-то задания необходим некий набор навыков S. Так же, есть группа людей, владеющих некоторыми из этих навыков. Причем каждый чел. стоит разных денег.
Необходимо сформировать минимальную группу для выполнения задания, включающую в себя носителей необходимых навыков, но при этом по цене чтобы выходило минимально.
...
Рейтинг: 0 / 0
Задачи о покрытии множества, нужна библиотека или функция
    #37052979
Multy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Т.е. если есть например есть чуваки владеющие знаниями:

1 2 цена 10
2 4 цена 10
5 6 цена 10
и
1 2 3 цена 14
4 5 6 цена 14
нам брать вторых, а если
есть 1 2 3 4 5 6 цена 25 то этого?

Типа того что ли?
...
Рейтинг: 0 / 0
Задачи о покрытии множества, нужна библиотека или функция
    #37053238
DelphiLexx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MultyТ.е. если есть например есть чуваки владеющие знаниями:

1 2 цена 10
2 4 цена 10
5 6 цена 10
и
1 2 3 цена 14
4 5 6 цена 14
нам брать вторых, а если
есть 1 2 3 4 5 6 цена 25 то этого?

Типа того что ли?
угу
...
Рейтинг: 0 / 0
Задачи о покрытии множества, нужна библиотека или функция
    #37053430
Multy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
DelphiLexx,
Не знаю есть ли подобные функции. Поищи ресурсов много:

http://ru.wikipedia.org/wiki/Список_алгоритмов
http://ru.wikipedia.org/wiki/Boost
http://algolist.manual.ru/
http://alglib.sources.ru/
http://www.sources.ru/
http://www.codenet.ru/
http://www.delphikingdom.com/
и т.д.

Без извратов можно решить просто перебором.
...
Рейтинг: 0 / 0
Задачи о покрытии множества, нужна библиотека или функция
    #37055578
DelphiLexx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MultyDelphiLexx,
Не знаю есть ли подобные функции. Поищи ресурсов много:

http://ru.wikipedia.org/wiki/Список_алгоритмов
http://ru.wikipedia.org/wiki/Boost
http://algolist.manual.ru/
http://alglib.sources.ru/
http://www.sources.ru/
http://www.codenet.ru/
http://www.delphikingdom.com/
и т.д.

Без извратов можно решить просто перебором.
Спасибо
...
Рейтинг: 0 / 0
Задачи о покрытии множества, нужна библиотека или функция
    #37055692
DelphiLexx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Но к сожалению, я не нашел в этих пакетов решение задач поиска наименьшего покрытия множества.
...
Рейтинг: 0 / 0
Задачи о покрытии множества, нужна библиотека или функция
    #37057861
Multy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
DelphiLexxНо к сожалению, я не нашел в этих пакетов решение задач поиска наименьшего покрытия множества.

Не удивительно, чем специализированнее задача, тем менее вероятно найти для неё готовое решение.

Если тебе надо просто решить, то можно простым перебором. Если именно по теории множеств - видимо придётся думать...
...
Рейтинг: 0 / 0
Задачи о покрытии множества, нужна библиотека или функция
    #37058065
ShSerge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сюръективное, инъективное, биективное или гомоморфное, эпиморфное или изоморфное покрытие?
...
Рейтинг: 0 / 0
Задачи о покрытии множества, нужна библиотека или функция
    #37058087
Multy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ShSergeСюръективное, инъективное, биективное или гомоморфное, эпиморфное или изоморфное покрытие?

Я только два слова понял "или" и "покрытие"...
...
Рейтинг: 0 / 0
Задачи о покрытии множества, нужна библиотека или функция
    #37059249
DelphiLexx
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ShSerge,

обычное
...
Рейтинг: 0 / 0
Задачи о покрытии множества, нужна библиотека или функция
    #37060143
coffeesnake
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Ну это вариант задачи о комивояжоре (NP-полной), решается, например, методом ветвей и границ и пр. Я бы делал полным перебором в несколько потоков, т.к. в этих методах не силён.
...
Рейтинг: 0 / 0
11 сообщений из 11, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачи о покрытии множества, нужна библиотека или функция
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]