Разновидность проблемы ранца: как решить проблему равных подмножеств сумм в Java

Обновление: Читайте об оптимизации пространственной сложности решения динамического программирования в моей следующей статье здесь.

Ранее я писал о решении задачи о ранце с помощью динамического программирования. Вы можете прочитать об этом здесь.

Сегодня я хочу обсудить вариант КП: проблема равных подмножеств сумм разбиений. Впервые я увидел эту проблему в Leetcode - именно это побудило меня узнать и написать о KP.

Это постановка задачи (частично воспроизведена без примеров):

Учитывая непустой массив, содержащий только положительные целые числа, найдите, можно ли разбить массив на два подмножества так, чтобы сумма элементов в обоих подмножествах была равна.

Для полной постановки задачи, с ограничениями и примерами, проверьте проблему Leetcode.

Динамическое программирование

Как и в случае с KP, мы решим это с помощью динамического программирования. Поскольку это вариация КП, логика и методология во многом схожи.

Решение

Мы разместим наше решение в методе, который возвращает логическое значение - true, если массив можно разбить на равные подмножества, и false в противном случае.

Шаг 1: Защита от нечетной суммы массива

Обычно, если все числа в массиве складываются в нечетную сумму, мы можем вернуть false. Мы продолжаем, только если массив складывается до четной суммы.

Шаг 2: Создание таблицы

Далее мы создаем таблицу.

Строки таблицы представляют собой набор элементов массива, которые необходимо учитывать, а столбцы таблицы указывают сумму, к которой мы хотим прийти. Табличные значения являются просто логическими значениями, указывающими, можно ли получить сумму (столбец) с помощью набора элементов массива (строки).

Конкретно, строка i представляет набор элементов массива от индексов 0 до (i-1). Причина этого смещения 1 в том, что строка 0 представляет пустой набор элементов. Следовательно, строка 1 представляет первый элемент массива (индекс 0), строка 2 представляет первые два элемента массива (индексы 0–1) и т. Д. Всего мы создаем n + 1 рядов, включая 0.

Мы только хотим знать, можем ли мы суммировать ровно половину общей суммы массива. Таким образом, нам нужно только создать столбцы totalSum / 2 + 1, включая 0.

Шаг 3: Предварительное заполнение таблицы

Мы можем немедленно начать заполнять записи для базовых случаев в нашей таблице - строка 0 и столбец 0.

В первом ряду каждая запись, кроме первого, должна быть ложной. Напомним, что первая строка представляет собой пустой набор. Естественно, мы не можем получить какую-либо целевую сумму - номер столбца - кроме 0.

В первом столбце каждая запись должна быть истинной. Мы всегда можем легко достичь целевой суммы 0, независимо от набора элементов, с которыми нам приходится работать.

Шаг 4: Построение стола (суть проблемы)

Некоторая запись в таблице в строке i и столбце j является истинной (достижимой), если выполняется одно из следующих трех условий:

  1. запись в строке i-1 и столбце j является истинной. Напомним, что представляет собой номер строки. Следовательно, если мы в состоянии получить конкретную сумму с подмножеством элементов, которые у нас есть в настоящее время, мы также можем получить эту сумму с нашим текущим набором элементов - просто не используя дополнительные элементы. Это тривиально. Давайте назовем это prevRowIsTrue.
  2. Текущий элемент - это именно та сумма, которую мы хотим получить. Это тоже тривиально верно. Давайте назовем это ExactMatch.
  3. Если вышеуказанные два условия не выполняются, у нас есть один оставшийся способ достижения нашей целевой суммы. Здесь мы используем текущий элемент - дополнительный элемент в наборе элементов в нашей текущей строке по сравнению с набором элементов в предыдущей строке - и проверяем, что мы можем получить остаток от целевой суммы. Давайте назовем это canArriveAtSum.

Давайте распакуем условие 3. Мы можем использовать текущий элемент, только если он меньше нашей целевой суммы. Если они равны, условие 2 будет выполнено. Если оно больше, мы не сможем его использовать. Следовательно, первый шаг - убедиться, что текущий элемент <целевая сумма.

После использования нашего текущего элемента у нас остается остаток нашей целевой суммы. Затем мы проверяем, достижимо ли это, проверяя соответствующую запись в строке выше.

Как и в случае с обычным КП, мы хотим постепенно строить наш стол снизу вверх. Мы начнем с базовых вариантов, пока не достигнем окончательного решения.

Шаг 5: Возврат ответа

Мы просто возвращаем return mat [nums.length] [totalSum / 2].

Рабочий код

Спасибо за чтение!