Автор оригинала: Pankaj Kumar.
Проблема с суммой подмножеств-это распространенный вопрос для собеседования, задаваемый во время технических собеседований на должность разработчика программного обеспечения.
Это также очень хороший вопрос для понимания концепции динамического программирования.
Постановка Задачи О Сумме Подмножеств
Постановка проблемы заключается в следующем:
Given a set of positive integers, and a value sum S, find out if there exists a subset in the array whose sum is equal to given sum S
Массив B является подмножеством массива A, если все элементы B присутствуют в A. Размер подмножества должен быть меньше или равен родительскому массиву.
Давайте возьмем пример:
A = { 3, 2, 7, 1}, Sum = 6
Output: True
В этом случае подмножество {3, 2, 1} дает сумму 6. Следовательно, мы выводим true.
Наивный подход к решению проблемы суммы подмножеств
Наивный подход к решению этого вопроса состоял бы в том, чтобы просмотреть все возможные подмножества.
Для n элементов может быть 2^n подмножеств.
Как вы можете догадаться, это было бы очень, очень, очень неэффективно с точки зрения вычислений.
Динамическое программирование для решения задачи суммирования подмножеств
Чтобы решить проблему с помощью динамического программирования, мы будем использовать таблицу для отслеживания суммы и текущего положения.
Мы создадим таблицу, в которой будут храниться логические значения.
Строки таблицы указывают количество элементов, которые мы рассматриваем. Это означает, что в 3-й строке рассматриваются только первые три элемента.
В столбцах таблицы указана сумма, которую мы пытаемся получить.
Строки идут от 0 до длины массива.
Столбец переходит от 0 к сумме.
Размер таблицы равен [длина массива +1, сумма+1].
Это означает, что последняя ячейка будет иметь индекс [длина массива, сумма]. После заполнения таблицы наш ответ был бы в этой самой ячейке.
Давайте посмотрим на код:
Java – программа для решения задачи о сумме подмножеств
package com.JournalDev;
public class Main {
public static void main(String[] args) {
int[] arr = {3,2, 7, 1};
int sum =6;
boolean ans = subset_Sum(arr,sum);
System.out.println(ans);
}
public static boolean subset_Sum(int[] A, int sum)
{
int n = A.length;
boolean[][] M = new boolean[n + 1][sum + 1];
for (int i = 0; i <= n; i++) {
M[i][0] = true;
// sum 0 is true irrespective of the length of the array
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= sum; j++)
{
//two options are :
// the current element is a part of the subset.
// the current element is not a part of the subset.
if (A[i - 1] > j) {
M[i][j] = M[i - 1][j];
//if the array element is greater than the sum
//take the value from the previous entry
//that is [i-1][j]
}
else {
M[i][j] = M[i - 1][j] || M[i - 1][j - A[i - 1]];
// otherwise check the position T[i-1][j - A[i - 1]]
// that is we are trying to get the sum j-A[i-1] from the previous //row.
// if we are able to get a subset that gives the sum of j-A[i-1],
//then we can get a sum of j from ith row as
//current element is A[I-1].
}
}
}
return M[n][sum];
}
}
Вывод : верно
Объяснение кода
В первом цикле for мы устанавливаем значения 0-го столбца как true. 0-й столбец означает получение 0 в качестве суммы, что верно независимо от рассматриваемых элементов.
Для строки i рассматриваемыми элементами являются все элементы от A[0] до A[i-1]. Столбец j означает, что сумма, которую мы пытаемся получить, равна j.
Если текущий элемент больше суммы, это:
A[i - 1] > j
Мы берем значение из M[i – 1][j]. Значение будет истинным, если без учета текущего элемента (A[i-1]) мы сможем получить сумму j.
В другом случае мы смотрим на две позиции и выполняем операцию ИЛИ.
M[i][j] = M[i - 1][j] || M[i - 1][j - A[i - 1]];
Позиция M[i – 1][j] означает получение суммы j без добавления текущего элемента (A[i-1]).
Позиция M[i – 1][j – A[i – 1]] означает получение суммы j – A[i – 1] в предыдущей строке. Если мы сможем получить сумму j – A[i – 1] из предыдущей строки, то мы можем добавить в нее текущий элемент и получить сумму в виде j.
j - A[i - 1] + (A[i - 1]) = j
Поскольку мы выполняем операцию ИЛИ, если одно из двух верно, мы можем установить M[i][j] как истинное.
В конце концов мы возвращаем значение M[n][сумма] в качестве выходного.