부분 집합 문제 - 모든 자료?

Question

예 숙제/실험실 과제입니다. 나는 "역 추적 (backtracking)"을 사용하여 부분 합계 문제를 해결하기 위해 알고리즘을 찾는데 흥미가있다. (나는 이해할 수있다 : P).

누구나 유용한 자료가 있습니까? 나는 지난 1 시간 정도 인터넷 검색을하면서 실제로 사용할 수 있다고 생각되는 것을 많이 찾지 않았습니다. xD

감사합니다!

Answer 1

데이터를 벡터에 넣습니다.

그런 다음 벡터, 색인 및 합계와 같은 3 개의 인수가있는 루틴을 작성하십시오. 전화 다음 인수와이 루틴 : 루틴은 다음과 같은 작업을 수행해야합니다 0

벡터, 0 :

• 검사는 우리는 벡터 (인덱스 == 크기)의 끝에 도달합니다. 이 경우 즉시 반환 할 수 있습니다. 인수
• 통화 자체 : 벡터 인덱스 + 1, 합계 + 벡터 [인덱스] (이 경우에 우리는 벡터로 합계 인덱스에 요소를 추가하고 계속) 인수
• 통화 자체 : 내가 의도적으로이 알고리즘에서이 개 부분을 왼쪽

벡터, 인덱스 + 1, 합 (이 경우 우리는 합 인덱스에있는 요소를 추가 할 수 있지만 여전히 계속하지 않음) :

• 먼저 합계를 확인해야합니다. 0이면 올바른 하위 집합
• 을 찾았으므로 사용 된 요소에 대한 지식도 전달해야 합계가 0이면 하위 집합을 인쇄 할 수 있습니다. 이를 위해 STL :: set 사용을 고려하십시오.

또는 함수의 반환 값을 사용하여 올바른 하위 집합을 이미 찾았는지 여부를 확인할 수 있습니다.

알고리즘의 복잡도는 O (2^N)이므로 큰 세트의 경우 매우 느립니다.

재미있게 보내십시오.