부분합 문제에 대한 PHP 프로그램

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

하위 집합 및 질문을 위한 PHP 프로그램

재귀 솔루션 사용

예

으아아아

출력

으아아아

제공된 예에서 집합은 [1, 7, 4, 9, 2]이고 목표 합계는 16과 25입니다. 목표 합계가 25인 두 번째 호출은 false를 반환하여 합계가 25인 하위 집합이 없음을 나타냅니다. 따라서 출력은 첫 번째 호출에서 주어진 합계를 가진 하위 집합을 찾았습니다. 두 번째 호출에는 주어진 합계의 하위 집합이 없습니다.

동적 프로그래밍을 사용한 의사 다항식 시간

예

으아아아

출력

으아아아

제공된 예에서 세트는 [8, 15, 26, 35, 42, 59]이고 목표 합계는 50입니다. isSubsetSum($set, $n, $sum) 함수 호출은 true를 반환하며, 이는 집합에 목표 합계 50을 추가하는 하위 집합 [8, 42]가 있음을 나타냅니다. 따라서 코드는 주어진 합계로 하위 집합을 찾습니다.

결론

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

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

위 내용은 부분합 문제에 대한 PHP 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!