Распечатайте наборы равных сумм массива (проблема с разделами) с использованием динамического программирования

Опубликовано: 16 Января, 2023

Дан массив arr[]. Определить, можно ли разбить массив на два множества так, чтобы сумма элементов в обоих множествах была равна. Если это возможно, то выведите оба множества. Если это невозможно, то выведите -1.

Примеры :

Input : arr = {5, 5, 1, 11}
Output : Set 1 = {5, 5, 1}, Set 2 = {11}
Sum of both the sets is 11 and equal.

Input : arr = {1, 5, 3}
Output : -1
No partitioning results in equal sum sets.

Условие: Проблема с разделом

Подход:

В предыдущем посте обсуждалось решение с использованием рекурсии. В этом посте объясняется решение с использованием динамического программирования.
Идея состоит в том, чтобы объявить два набора: набор 1 и набор 2. Чтобы восстановить решение, пройдите назад по логической таблице dp, начиная с окончательного результата dp[n][k], где n = количество элементов, а k = сумма/2. Набор 1 будет состоять из элементов, которые вносят вклад в сумму k, а другие элементы, которые не вносят вклад, добавляются в набор 2. Выполните следующие шаги в каждой позиции, чтобы восстановить решение.

  1. Проверьте, верно ли dp[i-1][sum] или нет. Если это правда, то текущий элемент не дает вклада в сумму k. Добавьте этот элемент в набор 2. Обновите индекс i на i-1, а сумма останется неизменной.
  2. Если dp[i-1][sum] ложно, то текущий элемент вносит вклад в сумму k. Добавить текущий элемент в набор 1. Обновить индекс i на i-1 и суммировать на sum-arr[i-1].

Повторяйте вышеуказанные шаги до тех пор, пока не будет пройдена каждая индексная позиция.

Реализация:

Анализ сложности:

  • Временная сложность: O(n*k) , где k = sum(arr)/2
  • Вспомогательное пространство: O(n*k)

РЕКОМЕНДУЕМЫЕ СТАТЬИ