Sum-of-Subsets 문제

문제

합이 G가 되는 모든 element들의 합의 집합들을 찾아라

 

입력 

5 // data의 개수

21 // 합 G의 값

5

6

10

11

16 // data 값

출력

5, 6, 10,

5, 16,

10, 11,

 

 

경우의 수 문제로 최대한 적게 경우의 수를 찾을 수 있는 방법을 생각해야 한다.

합이 G를 넘어버리면 중간에 경우에 대한 계산을 중단하고 다른 경우의 수 즉, 방법으로 넘어가야 한다

 

처음 생각해낸 방법은 중간에 결과가 G를 넘어버리면 다시 back tracking으로 전으로 돌아가야 한다는 대략적인 밑그림이었다.

back tracking 을 사용한다면 State Space Tree (상태 공간 tree)를 생각해야 한다

 

상태 공간 tree의 각 상태를 어떻게 정의하는가에 대해서 생각해보았다. 

 

각각의 level : 해당 data가 계산에 포함 유무 

-> 포함된다면 data 값 아니라면 0

 

tree에서의 각 node : 

-> 계산에 포함시, data 값 아니면 0

 

생각은 tree처럼 하되 실제 구현은 data들을 담아놓은 1차원 배열 w로 구현

 

prunning의 기준을 나타내는 promising 함수를 통해 

1. G를 미만이므로 더 계산해준다

2. G가 되었으니 출력해준다

3. G 초과이므로 계산을 끝내고 다음 경우의 수로 넘어간다

를 판별해준다

 

n = int(input())
G = int(input())
sum_total = 0

w = list()
answer = list()


def promising(total):
    if total == G:
        return 2
    elif total < G:
        return 1
    else :
        return 0


def sum_of_subset(index, total):
    
    if promising(total) == 2:
        for i in answer:
            print(w[i], end=', ')
        print()
        return
    if promising(total) == 1:
        if index+1 > n:
            return
        answer.append(index+1)
        sum_of_subset(index+1, total+w[index+1])
        answer.pop(-1)
        sum_of_subset(index+1, total)
    if promising(total) == 0:
        return


w.append(0)
for i in range(0, n):
    tmp = int(input())
    w.append(tmp)

print(f'w = {w}')

sum_of_subset(0, 0)

 

남은 숫자들을 다 더해도 G를 못 넘는데 G를 넘을 때까지 계산을 해주는 것이 비효율적일 수도 있겠다

remain이라는 변수를 추가하여 promising 함수를 조금 변경하여 더 빨리 back tracking 할 수 있도록 만들어보자

 

값을 넣을 때, input_sum 이라는 data들의 합 변수를 만들어놓고

promising에서 remain을 계산하여 현재까지 total (합)과 remain을 더했을 때, G를 넘는지 안넘는지 판단한다

 

n = int(input())
G = int(input())
input_sum = 0


w = list()
answer = list()

w.append(0)
for i in range(0, n):
    tmp = int(input())
    w.append(tmp)
    input_sum += tmp

print(f'w = {w}')


def promising(total):
    remain = input_sum - total
    if total == G:
        return 2
    elif total < G:
        return 1
    elif total > G or  total + remain < G:
        return 0


def sum_of_subset(index, total):
    
    if promising(total) == 2:
        for i in answer:
            print(w[i], end=', ')
        print()
        return
    if promising(total) == 1:
        if index+1 > n:
            return
        answer.append(index+1)
        sum_of_subset(index+1, total+w[index+1])
        answer.pop(-1)
        sum_of_subset(index+1, total)
    if promising(total) == 0:
        return




sum_of_subset(0, 0)