2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3
 
 Re: Комбинаторная задача на сумму элементов множества
Сообщение03.02.2018, 22:26 
Аватара пользователя


26/05/12
1694
приходит весна?
Вот интересно, есть ли какой-нибудь способ быстро прикинуть сколько будет вариантов разбить заданное мультимножество (не обязательно последовательных чисел) на два с заданной суммой одной из половинок?

-- 03.02.2018, 22:40 --

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

 Профиль  
                  
 
 Re: Комбинаторная задача на сумму элементов множества
Сообщение03.02.2018, 22:55 
Заслуженный участник


28/04/09
1933
B@R5uk в сообщении #1289945 писал(а):
Вот интересно, есть ли какой-нибудь способ быстро прикинуть сколько будет вариантов разбить заданное мультимножество (не обязательно последовательных чисел) на два с заданной суммой одной из половинок?
Это же что-то вроде задачи о сумме подмножеств (одной из разновидностей задачи о рюкзаке)?

 Профиль  
                  
 
 Re: Комбинаторная задача на сумму элементов множества
Сообщение03.02.2018, 23:32 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Комбинаторная задача на сумму элементов множества
Сообщение04.02.2018, 11:37 
Аватара пользователя


26/05/12
1694
приходит весна?
B@R5uk в сообщении #1289945 писал(а):
Заводим массив нулей размером, равным сумме элементов.
В первом элементе массива должна быть единица, разумеется. Иначе все элементы так нулями и останутся.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 34 ]  На страницу Пред.  1, 2, 3

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group