2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3
 
 Re: Комбинаторная задача на сумму элементов множества
Сообщение03.02.2018, 22:26 
Аватара пользователя
Вот интересно, есть ли какой-нибудь способ быстро прикинуть сколько будет вариантов разбить заданное мультимножество (не обязательно последовательных чисел) на два с заданной суммой одной из половинок?

-- 03.02.2018, 22:40 --

Спросил и тут же придумал решение. Заводим массив нулей размером, равным сумме элементов. Дальше два цикла: во внешнем берётся элемент множества. Во втором цикле перебираются элементы массива начиная с последнего ненулевого элемента в сторону начала массива и содержимое каждой просмотренной ячейки добавляется к содержимому ячейки, сдвинутой вправо на величину элемента, взятого во внешнем цикле. Сложность $O(N\cdot S)$, где N — число элементов, а S — их сумма.

 
 
 
 Re: Комбинаторная задача на сумму элементов множества
Сообщение03.02.2018, 22:55 
B@R5uk в сообщении #1289945 писал(а):
Вот интересно, есть ли какой-нибудь способ быстро прикинуть сколько будет вариантов разбить заданное мультимножество (не обязательно последовательных чисел) на два с заданной суммой одной из половинок?
Это же что-то вроде задачи о сумме подмножеств (одной из разновидностей задачи о рюкзаке)?

 
 
 
 Re: Комбинаторная задача на сумму элементов множества
Сообщение03.02.2018, 23:32 
Аватара пользователя
EtCetera в сообщении #1289954 писал(а):
Это же что-то вроде задачи о сумме подмножеств?
Да, именно её я и решаю сейчас. На компьютере разумеется. А эту тему создавал в связи с попыткой оценить трудоёмкость одного из подходов, который оказался совсем неудачным. Кстати, спасибо за ссылку. Там тоже есть описание каких-то алгоритмов.

 
 
 
 Re: Комбинаторная задача на сумму элементов множества
Сообщение04.02.2018, 11:37 
Аватара пользователя
B@R5uk в сообщении #1289945 писал(а):
Заводим массив нулей размером, равным сумме элементов.
В первом элементе массива должна быть единица, разумеется. Иначе все элементы так нулями и останутся.

 
 
 [ Сообщений: 34 ]  На страницу Пред.  1, 2, 3


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group