부분 집합 합 문제는 컴퓨터 과학 및 동적 프로그래밍의 고전적인 문제입니다. 양의 정수 집합과 목표 합계가 주어지면, 작업은 해당 요소의 합이 목표 합계에 해당하는 주어진 집합의 하위 집합이 존재하는지 여부를 결정하는 것입니다.

부분합 문제에 대한 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를 반환합니다. 이는 집합에 목표 합계 50을 합산하는 하위 집합 [8, 42]가 있음을 나타냅니다. 따라서 코드의 출력은 다음과 같습니다. 주어진 합계의 하위 집합을 찾았습니다.

결론

결론적으로 부분집합 합 문제를 해결하는 데는 두 가지 접근 방식이 있습니다. 첫 번째 솔루션은 주어진 집합의 하위 집합이 목표 합계와 동일한 합계를 가지고 있는지 확인하는 재귀적 접근 방식입니다. 가능한 모든 조합을 탐색하기 위해 역추적을 활용합니다. 그러나 이 솔루션은 최악의 경우 기하급수적인 시간 복잡도를 가질 수 있습니다.

두 번째 솔루션은 동적 프로그래밍을 활용하고 상향식 방식으로 하위 집합 합계 문제를 해결합니다. 중간 결과를 저장하기 위한 테이블을 구성하고 주어진 합계를 가진 하위 집합이 존재하는지 효율적으로 결정합니다. 이 접근 방식은 O(n*sum)의 시간 복잡도를 가지므로 재귀 솔루션보다 더 효율적입니다. 두 가지 접근법 모두 하위 집합 합 문제를 해결하는 데 사용될 수 있으며, 동적 계획법 솔루션은 더 큰 입력에 대해 더 효율적입니다.