백준 12865 평범한 배낭 - 파이썬

배낭문제 계속 메모리초과가 난다. 어떤부분이 잘못됐는지 모르겠어서 알아보려고 한다.

1. 문제 정의

배낭에 넣는 물품은 무게 w와 가치 v를 갖는다. n개의 물품에서 총 v의 합이 최대가 되도록 선택하여 배낭을 채운다. 배낭은 weight_possible만큼의 무게를 견딜 수 있다. 물품을 중복해서 선택할 수 없다.

2. 아이디어

Full binary tree로 표현할 수 있다. 각 노드는 배낭에 담긴 물품의 총 w와 v를 저장하며 왼쪽 자식은 각 물품을 포함하는 경우, 오른쪽 자식은 포함하지 않는 경우로 나타낼 수 있다.

 

물품의 무게를 배열 w에, 가치를 배열 v에 저장할 때 레벨 k와 k+1의 노드는 다음 그림과 같이 표현한다.

 

가능한 물품의 w와 v를 저장

트리 구조

 

트리의 레벨은 0부터 시작하여 n까지 존재하며, 가능한 모든 경우는 리프노드에서 확인할 수 있다. 또한 k+1번째 레벨의 노드를 만들기 위해서 k레벨의 노드와 k+1번째 물품의 w와 v만 필요하다.

 

추가적으로 응용한다면 굳이 full binary tree를 만들지 않아도 될 것이다. 계산중 노드의 w가 weight_possible보다 커지면 그 다음 노드의 자식은 weight_possible보다 클 것이므로 더이상 자식 노드를 만들지 않아도 될 것이다. 

3. 자료형

물품을 쉽게 표현하기 위해, 물품을 표현하는 클래스를 정의했다.

class Burden:
    def __init__(self, w, v):
        self.w, self.v = w, v

    def __str__(self):
        return f'(w: {self.w}, v: {self.v})'

    def __add__(self, other):
        return Burden(self.w+other.w, self.v+other.v)

4. 구현

위 내용을 구현한 코드이다.

class Burden:
    def __init__(self, w, v):
        self.w, self.v = w, v

    def __str__(self):
        return f'(w: {self.w}, v: {self.v})'

    def __add__(self, other):
        return Burden(self.w+other.w, self.v+other.v)


# 입력부
n, weight_possible = map(int, input().split())
burdens = []
for i in range(n):
    w, v = map(int, input().split())
    burdens.append(Burden(w, v))


previous = [Burden(0, 0)]
for k in range(n):
    now = []
    for pNode in previous:
        if (pNode+burdens[k]).w <= weight_possible:
            now.append(pNode+burdens[k])
        now.append(pNode)
    previous = now

print(max(previous, key=lambda thing: thing.v).v)

 

뭐가 틀렸는지 이제 알아보자.

백준 12865 평범한 배낭 - 파이썬 : 트리가 안되는 이유