부분집합의 합 구하기

  • Sum-of-Subset Problem

    • 원소가 n개인 양의 정수 집합 w와 양의 정수 W가 주어졌을 때 합이 W가 되는 w의 부분집합을 모두 찾기

  • backtracking approach로 해결하기

    • 상태공간트리를 만들어 풀기 (리프 노드가 모든 부분집합이 됨)
    • 가지치기 전략을 사용하기
      → 검색하기 전에 정수 원소를 오름차순으로 정렬해 놓으면 노드의 유망여부를 탐색 가능하게 됨
      → i번째 레벨에서 wi+1은 남아있는 정수 원소 중에서 가장 작은 값
      → 남아있는 원소 합이 W보다 작다면 하위 노드는 더이상 방문 할 필요가 없다 (유망하지 않기 때문에)
      → weight를 레벨 i까지의 정수 합이라 하고 weight가 W와 같지 않다면 weight + wi+1 > W 이라면 그 노드는 유망하지 않음
      → total이 정수 원소의 합일 때 weight를 더했을 때 W와 같아지지 않으므로 weight + total < W 이라면 이 노드도 유망하지 않다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# i = level, subset의 weight, 남은 원소의 합 total
def sum_of_subsets (i, weight, total):
    n = len(w) - 1
    if (promising(i, weight, total)):
        if (weight == W):
            print(include[1: n+1])
        else:
            # left subtree
            include[i + 1] = True 
            sum_of_subsets (i+1, weight + w[i+1], total - w[i+1])
            # right subtree
            include[i + 1] = False
            sum_of_subsets (i+1, weight, total - w[i+1])

def promising(i,weight, total):
    if((weight + total >= W) and 
        (weight == W or weight + w[i+1] <= W)):
        return True
    else:
        return False