Подскажите алгоритм
Вес - функция аддитивная?
Если да, то просто сортируешь массив весов и выбираешь первые k.
Если нет, то уточни вопрос.
Если да, то просто сортируешь массив весов и выбираешь первые k.
Если нет, то уточни вопрос.
если вес это не аддитивная функция, то пишешь стандартный алгоритм поиска множества всех подмножеств мощности к. Его можно найти в интернет
пишешь стандартный алгоритм поиска множества всех подмножеств мощности ксамому то не смешно?
мне кажется что у нас изначально неизвестны веса каждой чушки.
а можно только взвешивать пачку из К.
а можно только взвешивать пачку из К.
ну хотябы так вешаешь N комбинаций, находишь все веса и всё.
ключевые слова: система линейных уравнений.
лучше в среднем можно, но в худшем случае всё равно что-то порядка N получится, ИМХО.
ключевые слова: система линейных уравнений.
лучше в среднем можно, но в худшем случае всё равно что-то порядка N получится, ИМХО.
если вес не аддитивен - то тут только перебор
не только. Зависит от того, какие правила сложения весов. Может, он мультипликативен - тогда тоже никакого перебора не надо.
в условии не сказано, что считать весом. Будем считать вес аддитивной функцией.
если человек сформулирует условие задачи, тогда можно будет подумать над тем, как построить аддитивный вес.
если человек сформулирует условие задачи, тогда можно будет подумать над тем, как построить аддитивный вес.
Вес - функция аддитивная?нет.
если бы это было так, я б уж сообразил что делать..
иначе сформулируем вопрос: где задана функция веса? Если она задана аналитически, возможно, удастся что-нибудь придумать. Если она задана таблично, самое разумное - пройтись по этой таблице и найти максимальный элемент.
если вес это не аддитивная функция, то пишешь стандартный алгоритм поиска множества всех подмножеств мощности к. Его можно найти в интернета как он называется?
или в чем, в 2х словах, его идея?
Скажу одним словом - перебор.
да, веса каждого объекта неизвестны
ну хотябы так вешаешь N комбинаций, находишь все веса и всё.вот это я не понял, можно поподробнее?
ключевые слова: система линейных уравнений.
Идея проста: перебрать все возможные комбинации из k элементов.
да, пожалуй, вы правы, в абстрактной постановке это только перебор.
хорошо, сейчас попробую детализировать...
Можно считать, что сущности - это строки длины N из нулей и единиц.
Функция веса - это число единиц в побитовом "или" всех таких наборов.
хорошо, сейчас попробую детализировать...
Можно считать, что сущности - это строки длины N из нулей и единиц.
Функция веса - это число единиц в побитовом "или" всех таких наборов.
да, я понимаю. Но как это лучше сделать с программисткой точки зрения?
О! Что-то похожее на военной кафедре изучали. Может у кого осталось описание алгоритма?
тогда вес набора, хоть и неаддитивен по отношению к весам элементов, неубывающе зависит от их весов. Короче, чем тяжелее строки, тем тяжелее набор. Надо взять набор из k самых тяжелых строк.
Надо взять набор из k самых тяжелых строк.но это же неверное утверждение
почему?
может, у тебя не "или" а "исключающее или"? Если просто "или", то верное
может, у тебя не "или" а "исключающее или"? Если просто "или", то верное
1110
1110
0001
Выбираем две самые тяжёлые и обламываемся.
1110
0001
Выбираем две самые тяжёлые и обламываемся.
нет, я имел ввиду, что k самых тяжелых строк, вообще говоря, не есть решение.
во-во
да, пардон, нагнал
ё-маё, задача о минимальном покрытии практически.
она к этой сводится, а она НП-полна.
ПЕРЕБОР
хотя я тоже слегка нагнал, но жопой чую, что сводится
она к этой сводится, а она НП-полна.
ПЕРЕБОР
хотя я тоже слегка нагнал, но жопой чую, что сводится
да, готов согласиться.
тогда изменим задачу:
скажем, что нам необязательно самый максимум, можно не совсем уж максимальный набор, лишь бы найти его побыстрее. (т.е. хотим в некотором смысле рандомизированный алгоритм, допускаем возможность ошибки)
тогда изменим задачу:
скажем, что нам необязательно самый максимум, можно не совсем уж максимальный набор, лишь бы найти его побыстрее. (т.е. хотим в некотором смысле рандомизированный алгоритм, допускаем возможность ошибки)
Вот лучший манул по этой задаче, существующий в природе:
вот это уже можно и в инете поискать, для этого класса задач нагорожено уже много всяческих приближённых алгоритмов и эвристик. методы тут будут те-же самые что и в минимальном покрытии.
в этом документе решение задачи о минимальном покрытии с использованием эвристик, улучшающих перебор. Думаю, можно адаптировать некоторые идеи к задаче о максимальном покрытии k строчками
да, хороший текст, спасибо!
она к этой сводится, а она НП-полна.Ничего не сводится. При k=1 или k=N, например, задача решается тривиально...
пилять.
полный перебор тоже быстро работает, если перебирать нечего.
когда доказывают НП полноту задачи А то сводят за полином к этой задаче задачу Б про которую известно что она НП полна. типа если мы каким-то раком научимся быстро решать задачу А то мы тут-же научимся решать задачу Б, а раз никто ещё не придумал как быстро решать задачу Б то значит мы наверняка эту задачу А тоже быстро не решим.
чтоб решить задачу о минимальном вершинном покрытии будем просто перебирать К и пускать наше чудо решение задачи из этой темы, о чудо мы за полином решили задачу о минимальном вершинном покрытии.
полный перебор тоже быстро работает, если перебирать нечего.
когда доказывают НП полноту задачи А то сводят за полином к этой задаче задачу Б про которую известно что она НП полна. типа если мы каким-то раком научимся быстро решать задачу А то мы тут-же научимся решать задачу Б, а раз никто ещё не придумал как быстро решать задачу Б то значит мы наверняка эту задачу А тоже быстро не решим.
чтоб решить задачу о минимальном вершинном покрытии будем просто перебирать К и пускать наше чудо решение задачи из этой темы, о чудо мы за полином решили задачу о минимальном вершинном покрытии.
что то начал за здравие а кончил за упокой
да, хуйню какую-то написал, из этого абсолютно ничего не следует, надо чаще думать.
при фиксированном K вполне может существовать решение полиномиальное от N.
при фиксированном K вполне может существовать решение полиномиальное от N.
Задача на покрытие.
Можешь почитать книжку "Лекции по дискретной математике для студентов 4-го курса" Редькина.
У меня где-то была она, но сейчас найти не могу.
Можешь почитать книжку "Лекции по дискретной математике для студентов 4-го курса" Редькина.
У меня где-то была она, но сейчас найти не могу.
Да, в соответствии с формулой n!/(k!*(n-k)!) при фиксированном k имеем именно полиномиальную по n (а именно n^k) сложность полного перебора. Забавно
всё естественно, раз тут полином различных результатов.
эк меня занесло за NP...
вот что значит третий поток...
эк меня занесло за NP...
вот что значит третий поток...
Оставить комментарий
nikishina58
Нужно сделать следующее:есть n сущностей из них нужно выбрать k сущностей, с таким свойством, чтобы эта выборка обладала маскимальным весом. (считаем что у нас есть функция, позволяющая взвешивать любую комбинацию k сущностей).
Как можно написать такую программу?
Скажите плс в какую строну смотреть, где можно поискать решение?
(не отвечайте, плс, "ф_гугл", дайте хотябы кейвордс...)