두 그룹의 항목이 있다고 가정하십시오. 각 항목에 연결된 가중치가 있습니다. 그룹 B 항목의 조합에 대해 동일한 가중치 (또는 특정 허용 오차와 거의 같음)를 갖는 그룹 A 항목의 모든 조합을 찾고 싶습니다. 예를 들어, A1 + A2 항목은 B1과 동일하지만 A2가 B2 + B3 일 수도 있습니다. 이것을 위해 어떤 접근법을 사용할 수 있습니까?두 그룹에서 같은 무게를 가진 항목을 선택하십시오.
2n 개의 항목이 있다고 가정 할 때 각각의 무게는 1입니다. n 항목을 A에두고 나머지 항목을 B에 넣는 각 솔루션은 최적 부하 차이 0을 산출합니다. 그러나 그러한 솔루션은 2^n입니다.
이것은 일반적으로 최적 해의 수는 항목 수가 기하 급수적으로 증가 할 수 있음을 의미합니다. 결과적으로, 다른 제한이없는 한이 문제에 대한 알고리즘 ('항목의 수에 다항식으로 묶인 런타임'의 의미로)을 찾는 것은 불가능합니다.
여기서 동적 프로그래밍 알고리즘은 암시 적으로 검색 트리를 정리 (pruning)하는 것을 목표로하기 때문에 유용하지는 않습니다.
[서브 세트 합계 문제] (https://en.wikipedia.org/wiki/Subset_sum_problem)와 매우 유사하게 들립니다. 동적 프로그래밍 솔루션 (https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution)의 수정이 여기에서 효과가 있다고 생각합니다. – svick
이러한 모든 조합을 찾으려면 출력 크기가 지수가 될 수 있습니다. 그래서 어떤 알고리즘도 당신을 구할 수 없습니다. 무차별적일 수도 있습니다. 또는 모든 조합을 찾는 것을 포기하십시오. –
나는 여러 가지 서브 세트 합계 문제에 대해 [다항식 시간 근사 알고리즘] (http://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm)을 사용하여 실행 가능한 솔루션을 얻을 수있었습니다. 그러나 내 그룹은 크기가 한정되어 있습니다 (<20 개 항목). – andrei