[알고리즘] 부분집합 합 문제, sum of subsets problem

sum of subsets problem이란

n개의 양의 정수(w₁,w₂,...,w_n)와, 임의의 양의 정수 W가 있을 때, 다 합쳐서 W가 되는 모든 부분집합을 구하는 문제이다. 이 문제를 백트래킹을 사용하여 해결할 수 있다.

 

먼저 backtracking 문제를 풀기위해서는 상태공간트리의 구조와, 유망함수를 구축해야한다. sum of subsets 문제의 경우 상태공간트리의 구조와 유망함수는 다음과 같다.

 

① 상태공간트리의 구조

오름차순으로 level을 결정

 

② 유망함수(promising function)

weight + w_i+1이 W보다 큰가?  ≫ non-promising

weight + total이 W보다 작은가? ≫ non-promising

 

양의 정수들을 오름차순으로 정렬하고, 작은 것 부터 즉 w₁부터 w_n까지 순서대로 합쳐나가며 유망성을 검사한다. 작은 것들부터 먼저 넣어가는것이 유망성을 판단하기에 적합하다. 이 때, 현재까지의 합 weight에 다음 정수 w_i+1을 더한 값이 W보다 큰 경우 이는 유망하지 않다. 합이 W가 아니기 때문이다. 마찬가지로, 남아있는 모든 수 total을 weight에 합쳐도 W보다 작은 경우 유망하지 않다. 다 모아봤자 목표치에 달성하지 못한다는 뜻이기 때문이다.

 

수도코드

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"; //왼쪽 자식이면 yes(포함하는 경우) 
      sum_of_subsets(i+1, weight+w[i+1], total-w[i+1]); //포함했으므로 현재 무게에 w[i+1] 추가, 남은 무게에서 w[i+1] 제외
      include[i+1] = "no"; //오른쪽 자식이면 no(포함하지 않는 경우)
      sum_of_subsets(i+1, weight, total-w[i+1]); //포함하지 않으므로 weight 그대로
    }
}

bool promising (index i) { //유망성 검사
  return (weight+total >= W)
        && (weight == W || weight+w[i+1] <= W);
}