Как я могу найти элементы в массиве целых чисел, которые складываются в K? - PullRequest
Новая
       36

Как я могу найти элементы в массиве целых чисел, которые складываются в K?

0 голосов
/ 07 марта 2019

Дан массив целых чисел и число k. Найдите комбинацию элементов в массиве, которые складываются в k. Недавно я получил вопрос о кодировании, где мне дали массив натуральных чисел A и k.

Пусть A = {4, 15, 7, 21, 2} и k = 13 и мой алгоритм должен был вернуть список индексов элементов, которые складываются в k. В этом случае: [0,2,4]. Каждый элемент может быть использован только один раз.

Как бы я подошел к решению этой проблемы? Также, что бы сложность времени и пространства.

1 Ответ

2 голосов
/ 07 марта 2019

Это решение динамического программирования для этой проблемы, и я кодировал его для Emercoin в пределах оптимизатор транзакций .

Идея алгоритма: Вы создаете массив из элемента [k + 1].Индексом в этом массиве является сумма, которой может быть достигнуто некоторое входное значение, а значением в массиве - номер ввода, используемый для достижения этой суммы.Значение -1 показывает, что эта сумма не может быть достигнута текущим подмножеством элементов.

Давайте посмотрим на ваш пример.В вашем примере k = 13, и мы изначально создаем массив DP из 14 из -1:

DP = (-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1)

пустой выходной набор (сумма = 0) может быть достигнут любым способом, и из-за этого мы помещаем в DP [0] некоторое не минус_1, например - 0в результате DP [0] == 0:

DP = (0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1)

После этого для всех входных значений из вашего массива A [i] выполните следующее:

  • итерируйте массив DP в обратном направлении
  • , если DP [j]> = 0&& DP [j + A [i]] <0, тогда DP [j + A [i]] = i; </li>

Есть идея: если сумма «j» была достигнута на каком-то предыдущем шаге,и у нас есть значение A [i], тогда можно получить сумму «j + A [i]», добавив i-й элемент из массива A.

В нашем примере после добавления вашего A [0] == 4, у нас будет DP:

DP = (0 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1)

Этот ноль означает: сумма «4» может быть достигнута с помощью A [0].

Попытка добавить A [1] = 15. Существует два возможных местоположенияn для i = 1, DP [19] и dp [15].Оба выходят за пределы массива, поэтому мы просто не обновляем массив DP.

Попытка добавить A [2] = 7. Существует два возможных местоположения для i = 2, DP [11] и dp [7].После обновления массив DP будет:

DP = (0 -1 -1 -1 0 -1 -1 2 -1 -1 -1 2 -1 -1)

Пропустить A[3] == 21, так же, как A [1].

Попытка добавить A [4] = 2. Массив DP будет:

DP = (0 -1 4-1 0 -1 4 2 -1 4 -1 2 -1 4)

Входной массив A [] выхлоп, массив DP готов к интерпретации.Видим, DP [13]> = 0, поэтому сумма 13 достигнута.DP [13] == 4, поэтому сумма "13" достигается A [4].Помни это.Рассмотрим массив DP как связанный список, где значение относится к предыдущей позиции.Итак, prev = 13-2 = 11. Видим, A [2] также входит в сумму.помните "2".Предыдущая позиция: prev = 11-7 = 4. См. DP [4].есть "0".помните [0] тоже.Prev = 4-4 = 0. Мы достигли DP [0], остановите интерпретацию.Таким образом, мы собрали запомненные индексы в A [4,2,0].

Проблема решена.

...