@Mind31

Имеется набор чисел, нужно распределить их по группам, чтобы сумма входящих в каждую группу чисел была равна 10.

Например:
1, 3, 8, 4, 2, 2

группа 1: 8, 2
группа 2: 1, 3, 4, 2

если есть несколько вариантов сочетаний или сумма 10 не получается, то выбирать ту комбинацию, в которой будет больше полных групп (с суммой 10).

Не пойму, как к такой задаче подступиться, кроме как полным перебором с рекурсией (что нежелательно, т.к. исходный набор может быть большим и число 10 может быть тоже больше).
Подскажите.

0

@wer1

Уважаемый Mind31,
если бы мне пришлось решать эту задачу, то я сделал бы следующее
1. нашел общую сумму всех чисел
2. если сумма по модулю 10 не равна 0, то стал бы искать числа, входящие в остаток. Пример... допустим общая сумма равна 51 и среди чисел есть число 1, это значит, что это число 1 не войдет ни в одну группу. То есть число 1 можно сразу отбросить. Пример (продолжение)... итак сумма равна 51, но числа 1 среди всех чисел нет. Тогда мы будем искать группу, сумма чисел которых равна 11. (не 21, не 31, не ...). Если такая группа найдется (да, здесь перебор - Но это не тотальный перебор)... В общем принцип решения вашей задачи таков - "Разделяй и властвуй".

1

@Shamil1

Дано 9 1 41
Единственная комбинация 9 1, но Вы её сразу отбросили.

1

@sabrus

щас решаю практически ту же задачу )))
пока решения нет, но:
1. стопудово задача хрестоматийная, так что буду смотреть книги по алгоритмам
2. самостоятельно намечал решение так(знаю что неправильно):
допустим есть 1,2,3,4,5,6,7,8,9,12 надо набрать по 10.
- определить n_min n_max два параметра определяющих каким минимальным и максимальным количеством элементов может быть набрана сумма(складываем с одной стороны сортированной коллекции, получаем что 10 можно набрать за 1+2+3+4 = 4шт(n_max=4), с другой 12+9>10(n_min=2), т.е. для данной выборки надо рассматривать сочетания С2из10,С3из10,С4из10, т.е. нужно перебрать эти варианты(все равно получается достаточно толстый алгоритм).
https://www.matburo.ru/tvart_sub.php?p=calc_C

- формируем комбинации, чекаем.

Добавлено через 17 минут
нашел чье то решение, буду тестить...
http://blog.kislenko.net/show.php?id=1083

0

@wer1

Уважаемый sabrus,
я полагаю, что изначально надо отбросить все числа большие 10...
Ведь они точно не будут ни в одной группе!

0

@Sindbad_M

...затем выбрать все числа равные 10, ведь каждое из них образует группу

затем можно проверить формируют ли группы с суммой десять какие-нибудь пары чисел, найденные пары исключить из дальнейшего рассмотрения

из оставшихся чисел исключить все девятки

оставшиеся числа проверить, образуют ли какие-нибудь три из них сумму равную десяти, найденные тройки исключить

из оставшихся чисел исключить восьмерки

из оставшихся найти четверки с суммой десять и т.д.

Добавлено через 8 минут
хотя нет, ерунду написал, не будет это работать

1

@wer1

Уважаемый Sindbad_M,
вы классно подошли к решению этой задачи
1. во-первых вы совершенно верно начали с рассмотрения чисел в порядке убывания
2. во-вторых ... поскольку нам надо максимальное количество групп ... вы совершенно
логично предложили рассматривать пары чисел
3. в-третьих (да перебора нам не избежать) ... вы предложили Самый лучший вариант
поиска решения!!!
Я вам очень благодарен за ваши рассуждения и мысли в решении этой задачи!

0

@sabrus

НТЧ, программирование явно не ваш хлеб, простите за прямоту.Причем тут пары? Пары надо смотреть если С2изN имеет место, иначе толку от пар никакого. Причем тут убывание???? В чем тут "совершенно верно"??

0

@Sindbad_M

sabrus, за прошедшие несколько часов я не смог ни придумать строго обоснования своего алгоритма, ни какого-нибудь контрпримера, когда алгоритм не находит верного решения. Если у вас есть контрпример для пар, приведите его.

0

@sabrus

т.е. есть в наборе 1,1,1,6,2,2,4 надо набрать 10. 6+4=10? ок. записали в результат и исключили, а если бы не исключили то могло бы быть:

2+2+4+1+1, 6+2+2, 6+1+1+2, думаю мысль понятна.

ps/ по ссылке что я привел выше - лажа, кривущщая.
Решается это рекурсией, и как правило если задача приходит из реальной постановки, то есть условие для оптимизации кол-ва рассматриваемых сочетаний.

0

@Sindbad_M

Не подходит. В данном примере можно сформировать не более одной полной группы. Пара {6,4} такую группу находит, условие задачи выполнено.

0

@sabrus

и

взаимоисключающие высказывания. )

0

@Sindbad_M

Дан набор чисел {1, 1, 1, 2, 2, 4, 6}
Ищем в нем пары, дающие в сумме 10.
Нашли первую пару: {4, 6}, это есть первая полная группа, сохранили найденную группу где-то, где храним информацию о группах
исключаем найденную пару, получаем набор чисел {1, 1, 1, 2, 2}
ищем пары в оставшемся наборе, не находим, переходим к следующему шагу алгоритма.
По заврешении алгоритма имеем:
- не смогли разделить весь исходный набор чисел на полные группы
- найденное максимальное количество полных групп - одна.

Что тут взаимоисключающее?

0

@sabrus

6+1+1+2 будет решением?*
как оно будет получено, если мы 6 исключили на первом шаге?

PS/
все, я расшифровал ваш ломанный русский...это тоже самое что предложил я. Но вы по незнанию комбинаторики не поняли что я писал.
C2из10 это по-вашему "пары", С3из10 это уже "тройки"....детсад какой то чесслово..."пара" называется: сочетание 2 из 10
и еще.
подумайте над тем что я написал первым пунктом(n_min и n_max), чтобы не гадать будут ли пары, тройки и т.п. или не будут...

0

@woldemas

0

@sabrus

0

@Sindbad_M

По условию задачи, решением является какое-нибудь разбиение исходного набора, удовлетворяющее определенным условиям. Задачи найти все возможные разбиения, подходящие под условия, не ставилось.

Да, не понял, еще раз обдумал, все равно не вижу в вашем сообщении вообще никакого алгоритма. Речь ведь об этой паре строчек?



Во-первых непонятно, как из отношения 12+9>10 следует n_min=2 ??

А если будет дан набор {2,2,3,5,6,9,12 } n_min тоже двум равняется?

Вообще непонятен алгоритм нахождения n_min и n_max. Можно, конечно, найти n_min и n_max полным перебором всех сочетаний элементов исходного набора. Но тогда непонятно зачем их искать, для чего нужны эти числа?

Далее совсем непонятно. Фраза "рассматривать сочетания С2из10,..." математически безграмотна. Политкорректно назовем её небрежной. Символом "Цэ", точнее обозначают количество сочетаний содержащих k элементов n-элементного множества. Например это число 45. Если вы предлагаете рассмотреть числа 45, 120, 210, то непонятно что с ними делать, как эти числа помогут найти требуемой разбиение набора на полные группы. Далее я предположил, что вы имели в виду не количество сочетаний, а предлагали рассмотреть множество всех двух, трех и четырехэлементных сочетаний исходного набора (символ "Цэ" в этом случае, конечно, был неуместен). Но ведь совершенно непонятно что делать с каждым из сочетаний. Их можно, например, разделить на те, которые образуют полную группу и остальные, которые группы не образуют. Но как это поможет найти способ разбить исходный набор на группы - непонятно. Например, дан набор {1,2,2,4,5,6,6}
Перебирая пары двухэлементные сочетания, найдем, что из всех 21 сочетаний два образуют полную группу: {4,6} и {4,6}
Перебирая тройки сочетания из трех элементов, найдем, что из 35 сочетаний три образуют полную группу
Перебирая сочетания из четырех элементов, найдем еще одну полную группу.
Где вы говорите как дальше поступить со всем этим? И как вообще это приближает к решению задачи?

Короче говоря, я до сих пор не понимаю что вы писали, вне связи со знанием комбинаторики.

Добавлено через 6 минут
Нельзя так вольно с терминами. Сочетание это подмножество, не может быть "вычислено" подмножество, не может. А вот количество подмножеств можно посчитать.

0

@sabrus

"Диагноз: психических отклонений нет. Просто дурак"

0

@vrm2

В общем виде точное решение этой задачи без перебора не получить. Задача NP полна, т.к. если мы научимся за полиномиальное время решать эту задачу, то сможем решить и Задачу разбиения множества чисел (которая NP-полна)

Думаю, существует псевдополиномиальное решение, но все может усложниться, если, как Вы говорите, исходный набор и целевая сумма может быть больше.

0

@Shamil1

По условию задачи нужно распределить числа по группам. Искать все возможные распределения не требуется.

0