부분 집합 솔루션 향상

Question

주어진 값과 주어진 숫자 배열이있는 연습 문제가 있습니다. 주어진 배열에있는 값 중 하나를 사용하여 주어진 값과 동일한 합을 만들 수 있습니다.

원본, 내 알고리즘은 모든 가능한 조합에 대해 배열을 반복합니다. 나중에 현재 합계가 값보다 큰지 확인하기 위해 최적화되었습니다. 그럴 경우 후자의 조합을 모두 시도해보십시오. 모두 값보다 커야합니다.

호기심에서 처음으로 모든 합계를 계산 한 다음 합계를 정렬하고 같은 값의 합을 찾기 위해 이진 검색을 수행하는 것이 더 좋을까요? 매 한자리 수를 비교할 때 합계를 미리 계산하고 결과를 비교하는 것보다 훨씬 느릴 것이라고 생각합니다.

Answer 1

모든 합계를 계산 한 다음 원하는 값과 같은 합계를 검색하는 것이 간단한 무차별 강제 검색보다 시간이 더 효율적입니까?

그런 세트가없는 최악의 경우를 고려하면 솔루션의 모든 합계를 이미 계산 중이므로 두 세트의 솔루션에 대해 수행해야 할 추가 연산의 수는 동일합니다. 검색은 결국 모든 조합을 시도합니다.

솔루션에서 비교 한 횟수가 무차별 대입을 사용하여 비교 한 횟수보다 적습니까? 예. 먼저 모든 합계를 계산할 필요가 없으며 그 다음 결과를 정렬합니다. 모든 계산을 수행하는 동안 정렬 된 집합을 간단하게 작성할 수 있습니다. Brute-forcing은 조합 수만큼 많은 비교를 수행하지만 결국 모든 합계의 정렬 된 콜렉션을 작성한 다음 일치하는 값에 대한 2 진 검색을 수행하면 지수가되어서는 안됩니다.

그런데 다시 파워 셋을 구축하는 동안 해결책을 찾았을 것입니다. 따라서 단순한 무차별 공격과는 얼마나 다른지 잘 모르겠습니다. 당신이 그렇게 선택한다면, 당신은 모든 합계와 다른 중개 계산을 저장해야하기 때문에 더 비싼 짐승처럼 보입니다.