Разделите набор чисел на k подмножеств так, чтобы значения были распределены равномерно

Возможный дубликат:
алгоритм равных k подмножеств

Скажем, у меня есть набор чисел, я хочу разделить числа на k подмножеств, чтобы числа были распределены равномерно. Под равномерно распределенным я подразумеваю, что сумма значений в подмножествах наиболее близка к другим суммам других подмножеств. Можем ли мы реализовать DP-решение этой проблемы??

Пожалуйста, предложите!


algorithm dynamic-programming subset-sum
person 4sh1sh    schedule 05.09.2011    source источник
comment
Известно, что эта задача является NP-трудной. Являются ли числа целыми? Или произвольные действительные числа?   -  person templatetypedef    schedule 06.09.2011
comment
Я склонен думать, что не имеет значения, целые они или нет. Поскольку единственной операцией является сложение, любую задачу с действительными числами можно масштабировать/возмущать до эквивалентной задачи только с целыми числами.   -  person Mysticial    schedule 06.09.2011
comment
@Mystical- Это действительно имеет значение. Не все задачи, связанные с вещественными числами, можно адаптировать для работы с целыми числами; например, линейное программирование в P, в то время как целочисленное программирование в NP-сложно и, как предполагается, не имеет решения за полиномиальное время. В этом конкретном случае может существовать решение DP, основанное на целых числах, которое не работает для действительных чисел. Задача о рюкзаке, например, может быть решена за псевдополиномиальное время с помощью DP, а задача о рюкзаке для вещественных чисел — нет.   -  person templatetypedef    schedule 06.09.2011
comment
@templatetypedef: точка принята. У меня сложилось впечатление, что, поскольку задействовано только сложение (сложение не может генерировать нецелые числа из целых чисел), можно масштабировать всю задачу так, чтобы различия между всеми числами были значительно больше единицы, при которой все можно округлить до целое число. Моя ошибка в том, что это верно только в том случае, если все числа имеют конечную точность для начала (в компьютере).   -  person Mysticial    schedule 06.09.2011
comment
@templatetypedef Можете ли вы предложить какой-либо алгоритм приближения, если числа целые??   -  person 4sh1sh    schedule 06.09.2011
comment
@charlesworth Это совершенно другая проблема, в ней не говорится, что подмножества имеют равные суммы, но суммы должны быть ближе всего друг к другу.   -  person 4sh1sh    schedule 06.09.2011
comment
@4sh1sh: страница википедии предлагает некоторое приближение к этой проблеме, которая является проблемой раздела . Другие возможности: SAHC и генетические алгоритмы. Если вы укажете, зачем вам это нужно, мы сможем предложить, какая эвристика лучше подходит для вашей цели.   -  person amit    schedule 06.09.2011

Ответы (1)


arrow_upward
-1
arrow_downward

Все, что я могу предложить, это моя лучшая попытка, вот она:

Мне кажется, что если m — размер вашего множества, то m/k = n; что является количеством элементов в каждом наборе.

Теперь я предполагаю, что вы работаете с целыми числами, допустим, мы имеем набор, s:

s ={1,2,3,4,5,6,7,8}

Теперь это простая идея, что если вы отсортировали набор, то сумма позиций
-Sum(0 и last-0) = Sum(1,Last-1) = Sum(2,last-2) = Sum (3,последнее-3)... и так далее.

переменные будут:

  • m = 8
  • k = 2 (для примера)
  • n = 4

поэтому нам нужно 4 набора: s1 = 1,8 = сумма равна 9 s2 = 2,7 = сумма равна 9 s3 = 3,6 = сумма равна 9 s4 = 4,5 = сумма равна 9

Теперь, конечно, будет некоторая хитрость, если размер множества нечетен и/или если k нечетно, но с ними можно справиться, используя специальные случаи, реализуя ситуацию, которая лучше всего подходит для вашей конкретной цели.

Надеюсь, это даст вам толчок в правильном или почти в любом направлении.

person Aziz    schedule 05.09.2011
comment
Вы не можете точно сказать, что Sum(0 and last-0) = Sum(1,Last-1) = Sum(2,last-2) = Sum(3,last-3)... и так далее всегда верно в отсортированный набор целых чисел. Просто возьмем простой случай этого набора {1,1,1,1,1,99} . И ваш алгоритм не работает лучше всего со многими простыми случаями, скажем, у нас есть S = {1,2,2,4,8,10} и k = 3. Ответ в соответствии с вашим подходом: {{1,10},{2,8},{2,4}}. Решением в этом случае будет {{1,2,2,4},{8},{10}}. Это не обязательно должно быть одинаковое количество целых чисел в каждом подмножестве, они могут различаться. - person 4sh1sh; 06.09.2011