알고리즘: 부분집합의 합(sum of subset) 공부하기!(Backtracking 문제)

부분집합의 합 구하기 문제에서는 양의 정수(무게) wi가 n개와 양의 정수 W가 있다.

 

합이 W가 되는 정수의 부분집합을 모두 찾는 것이 목표다.

 

전에 다루었던 knapsack문제와 유사하지만 부분집합의 합 구하기 문제에서는

조건을 만족하는 모든 집합을 찾는다는 점에서 다르다. 

 

 

알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem)

 

 

 

예를 들어보자

 

n = 3, W =6

w1 = 2, w2 = 4, w3 = 5 이라 할때

 

각 노드들의 합이 6이 되는 모든 경우를 찾아보면 {w1, w2}가 있다.

 

 

 

이 사례를 검사해서 풀어보자.

 

wi를 포함하는 이음선 상에는 wi라 표현하고, 그렇지 않은 이음선에는 0을 표기한다. 

 

 

 

 

 

 

이를 일반화시키기 위해 검색하기 전에 오름차순으로 가중치를 정렬한다.

(정렬함으로써 유망하지 않은 노드를 확인할 수 있게 되므로)

 

 

weight를 지금까지의 합이라 할때 다음의 경우가 유망하지 않게 된다. 

 

 

 

 

 

위의 조건을 이용하여 간단한 예제를 풀어보자.

 

n =4, W =13, w1 =3, w2 =4, w3 = 5, w4 =6이라고 할때 만족하는 집합을 찾는다. 

 

(유망하지 않은 노드들은 x라고 표시하자)

 

 

 

 

 

sum of subset 수도코드 

void sum_of_subsets(index i, int weight, int total){
	if(promising(i)){
    	if(weight == W)
        	cout << include[1] through include[i];
        else{
        	include[i+1] = "yes";
        	sum_of_subsets(i+1, weight + w[i+1], total-w[i+1]);
        	include[i+1] = "no";
        	sum_of_subsets(i+1, weight, total-w[i+1]);
        }
    
    }
    
bool promising (index i){
	return (weight + total >= W) && weight + w[i+1] <= W);

}
}

 

출처 : Foundations of Algorithms, Using C++ Pseudocode