Задача динамического программирования .. Разбиение массива ..

Вопрос гласит:

Учитывая массив размера n, мы должны вывести / разделить массив на подмножества, сумма которых равна N.

For E,g, 
    I/p  arr{2,4,5,7}, n=4, N(sum) = 7(given)
    O/p = {2,5}, {7}

Я видел подобную проблему / объяснение в URL-адресе Dynamic Programming3

И у меня есть следующие запросы в pdf: -

  1. Как мы могли бы найти подмножества, сумма которых равна N, поскольку логика только говорит, существует ли подмножество или нет?
  2. Кроме того, если мы немного изменим вопрос, сможем ли мы найти два подмножества с одинаковым средним значением, используя одну и ту же идеологию?

Может ли кто-нибудь пролить свет на эту проблему динамического программирования .. :)

Заранее спасибо..


c algorithm bin-packing dynamic-programming
person AlgoGeek    schedule 27.06.2011    source источник
comment
en.wikipedia.org/wiki/Bin_packing_problem   -  person Peter G.    schedule 27.06.2011
comment
Привет, Питер, я ничего не получил с этой вики-страницы .. Предоставлено недостаточно информации ...   -  person AlgoGeek    schedule 27.06.2011
comment
На самом деле, ближе к en.wikipedia.org/wiki/Cutting_stock_problem. В задаче об упаковке бункера достаточно, если Σai ≤ V, но здесь условие Σai = N.   -  person MSalters    schedule 27.06.2011

Ответы (3)


arrow_upward
1
arrow_downward

Вы можете попробовать выполнить рекурсивную обработку:

Для СОРТИРОВАННОГО массива X = {x1 ... xn} xi! = 0 и целого числа N.

Сначала найдите все возможности, "реализованные" с помощью всего лишь одного элемента:

здесь, если N = xp, исключить все xi s.t i> = p

второй найти все возможности, сделанные с помощью 2 элементов:

{ (x1,x2) .... (xp-2,xp-1)}

Отсортируйте по сумме и выведите все суммы> = N, и у вас были правила: xi не может идти с xj, когда xi + xj> = N

Третий с 3 элементами: вы создаете все части, которые соблюдают указанное выше правило. И идем, шаг 2 и т. Д.

Пример:

X={1,2,4,7,9,10} N=9

step one:
{9}
X'={1,2,4,7,9}

step 2: cannot chose 9 and 10
X={(1,2) (1,4) (2,4) (1,7) (2,7) (4,7)}
{2,7}
X'={(1,2) (1,4) (2,4) (1,7)}

step 3: 4 and 2 cannot go with 7:
X={(1,2,4)}
no sol

{9} {2,7} are the only solutions

Это уменьшает общее количество сравнений (это будет 2 ^ n = 2 ^ 6 = 64), которые вы сделали: 12 сравнений

Надеюсь, поможет

person Ricky Bobby    schedule 27.06.2011
comment
Единственная проблема с этим методом заключается в том, что с большим массивом значений, когда вы прекратите попытки с все большим и большим количеством чисел? До тех пор, пока подмножества, которые вы пытаетесь создать, не станут равными или превышающими оставшиеся значения, вы должны продолжать выполнять сравнения. Кроме того, это запускает множество сравнений снова и снова для меньших наборов, когда значения будут использоваться позже в более крупном наборе. Например, если у вас есть числа, равные N в наборе из 15 целых чисел, но меньшие, чем это, они не создают набор, вы выполняете большое количество сравнений от 0 до 15, пока не дойдете до единственного работающего случая. - person SomeoneRandom; 27.06.2011
comment
Для более крупных наборов сравнение вы можете представить (я говорю представьте, потому что я не уверен, что это работает), комбинируя результаты, которые у вас были для небольших наборов, и используя правила, которые я определил выше. например, для наборов из 6 элементов: вы смотрите на X2 'и X4' (X 'я определил с 2 и 4 элементами) или X1' и X5 'или X3' и X3 '. Таким образом, это уменьшает количество повторных появлений наборов, состоящих из небольших целых чисел. - person Ricky Bobby; 27.06.2011

arrow_upward
1
arrow_downward

К сожалению, это очень сложная проблема. Даже определение , если существует единственное подмножество, суммирующее целевое значение, является NP-Complete.

Если проблема более ограниченная, вы можете найти хороший алгоритм. Например:

  • Должны ли подмножества быть смежными?
  • Можно ли игнорировать подмножества со значениями более K?
  • Гарантированно ли положительные значения массива?
  • Гарантируется ли различие значений массива? А как насчет того, чтобы отличаться от других значений хотя бы на какой-то постоянный коэффициент?
  • Есть ли какая-то граница разницы между наименьшим и наибольшим значением?
person Craig Gidney    schedule 27.06.2011

arrow_upward
0
arrow_downward

Предлагаемый алгоритм хранит только один бит информации во временном массиве T[N], а именно, достижим ли он вообще. Очевидно, что вы можете хранить больше информации по каждому индексу [N], например, значения C[i], используемые для этого. (Это вариант главы "Работа с неограниченным количеством копий" в PDF-файле)

person MSalters    schedule 27.06.2011