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

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

2 голосов
/ 27 июня 2011

В вопросе говорится:

При заданном массиве размера n мы должны вывести / разбить массив на подмножества, которые составляют N. 

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

Я видел похожий видПроблема / объяснение в URL Динамическое программирование3

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

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

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

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

Ответы [ 3 ]

1 голос
/ 27 июня 2011

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

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

  • Должны ли подмножества быть смежными?
  • Можете ли вы игнорировать подмножества с более чем K значениями?
  • Значения массива гарантированно будут положительными?
  • Значения массива гарантированно различаются? А как насчет отличия от других значений хотя бы по некоторому постоянному коэффициенту?
  • Есть ли какая-то граница для различия между наименьшим и наибольшим значением?
1 голос
/ 27 июня 2011

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

С учетом отсортированного массива 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 сравнений

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

0 голосов
/ 27 июня 2011

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

...