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

PHP-программа для решения задачи о сумме подмножества

Использование рекурсивного решения

Пример

 $sum)
      return isSubsetSum($set, $n - 1, $sum);
   // Check if the sum can be obtained by either including or excluding the last element
   return isSubsetSum($set, $n - 1, $sum) ||
      isSubsetSum($set, $n - 1, $sum - $set[$n - 1]);
}
// Driver Code
$set = array(1, 7, 4, 9, 2);
$sum = 16;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
   echo "Found a subset with the given sum
";
else
   echo "No subset with the given sum
";
$sum = 25;
$n = count($set);
if (isSubsetSum($set, $n, $sum) == true)
   echo "Found a subset with the given sum.";
else
   echo "No subset with the given sum.";
?>

Выход

Found a subset with the given sum.
No subset with the given sum.

В приведенном примере набор — [1, 7, 4, 9, 2], а целевые суммы — 16 и 25. Второй вызов с целевой суммой 25 возвращает false, указывая на отсутствие подмножества. в сумме это дает 25. Таким образом, результат получился как «Найдено подмножество с заданной суммой при первом вызове». Нет подмножества с заданной суммой во втором вызове.

Псевдополиномиальное время с использованием динамического программирования

Пример

= $set[$i-1])
				$subset[$i][$j] =
					$subset[$i-1][$j] ||
					$subset[$i - 1][$j -
							$set[$i-1]];
		}
	}
	/* // uncomment this code to print table
	for (int i = 0; i 

Выход

Found a subset with given sum.

В приведенном примере набор равен [8, 15, 26, 35, 42, 59], а целевая сумма равна 50. Вызов функции isSubsetSum($set, $ n, $sum) возвращает true, указывая на то, что в наборе существует подмножество [8, 42], которое в сумме дает целевую сумму 50. Таким образом, выходные данные кода будут такими: Найдено подмножество с заданной суммой.

Заключение

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

Второе решение использует динамическое программирование и решает проблему суммы подмножества восходящим способом. Он создает таблицу для хранения промежуточных результатов и эффективно определяет, существует ли подмножество с заданной суммой. Этот подход имеет временную сложность O(n*sum), что делает его более эффективным, чем рекурсивное решение. Оба подхода могут использоваться для решения проблемы суммы подмножества, при этом решение динамического программирования более эффективно для больших входных данных.