백준 12865 번 배낭문제

//문제

 

K 만큼 담을 수 있는 배낭에

W의 무게와 V의 가치를 가진 물건들을 담을 때

최고로 가치있는 배낭을 만들면 배낭의 가치는 얼마인가

 

//사고

 

배낭문제는 크게 2가지로 나뉘는데

분할 가능 배낭 문제와 분할 불가능 배낭문제로 나뉜다.

분할 가능 배낭 문제는 말 그대로 물건을 쪼개서 넣을 수 있을 경우,

분할 불가능은 지금처럼 쪼갤 수 없는 물건들을 넣는 경우다.

 

보통 어떤 변수의 총량을 결정하는 단위를 찾을 수 있을 때

예를 들면 1kg으로 나눌 수 있거나 2kg 단위로 나눌 수 있을 때

그리디 방식을 사용하고 그럴 수 없을 때

다이나믹 프로그래밍, 그 중에서도 타뷸레이션 방법을 사용한다.

 

이 문제의 결우 타뷸레이션을 사용해서 쉽게 풀 수 있는 전형적인 문제다.

 

//풀이

 

N, K = list(map(int, input().split(" ")))

cargo = []
for _ in range(N):
    cargo.append(list(map(int, input().split(" "))))

def tabulation(cargo, capacity):
    pack = []
    for i in range(len(cargo) + 1):
        pack.append([])
        for c in range(capacity + 1):
            if i == 0 or c == 0:
                pack[i].append(0)
            elif cargo[i-1][0] <= c:
                pack[i].append(
                    max(
                        cargo[i-1][1] + pack[i-1][c - cargo[i-1][0]],
                        pack[i-1][c]
                    )
                )
            else:
                pack[i].append(pack[i-1][c])
    return pack[-1][-1]

r = tabulation(cargo, K)
print(r)

위의 풀이는 `파이썬 알고리즘 인터뷰[박상길 저]` 의 타뷸레이션 코드를 그대로 사용한 것이다.

pack이라는 테이블의 값을 채워넣어가면서 풀이를 진행하는 방식이다.

 

태블릿에 직접 표를 그려가면서 풀어보았다.

그러면 훨씬 더 머리에 잘 들어온다.

아무것도 없는 상태에서 시작해야 하기 때문에 한 줄씩 비워야 해서

cargo와 인덱스 차이가 1이 난다.

좌에서 우로는

가방의 용량이 K가 될 때까지 1씩 늘려가면서 담을 수 있는 최고의 가치를 찾는다.

상에서 하로는

이때까지 용량이 c인 가방에서 얻었던 최고의 가치를 물려받는다.

그러다보면 표를 다 채웠을때 우하단에 최고의 가치가 쌓이게 된다.

이때 cargo을 sort해 줘야 하지 않을까 라는 의문이 들 수도 있는데

물건을 넣는 순서와는 상관이 없기 때문에 (덧셈은 교환법칙이 성립하기 때문에)

표를 짜는 순서만 잘 정해주면 cargo의 순서를 굳이 바꿔줄 필요는 없다.

 

나는 이 문제를 처음 풀고 시간이 한참 지나 한번 더 풀게 되었는데

이 코드를 피해서 동일한 코드를 짜기 위해 아래와 같은 시도를 했다.

 

import sys

readline = sys.stdin.readline
N, K = list(map(int, readline().strip().split(" ")))

cargos = []
for _ in range(N):
    thing = list(map(int, readline().strip().split(" ")))
    cargos.append(thing)

def tabulatation(cargos, capacity):
    pack = [0 for _ in range(capacity + 1)]
    pack = [pack[:] for _ in range(len(cargos) + 1)]

    for i in range(len(cargos) + 1):
        for j in range(capacity + 1):
            if i == 0 or j == 0:
                continue
            else:
                cur_weight, cur_value = cargos[i-1]
                if cur_weight <= j:
                    pack[i][j] += max(
                        cur_value + pack[i-1][j - cur_weight],
                        pack[i-1][j]
                    )
                else:
                    pack[i][j] += pack[i-1][j]
    return pack[i][j]

r = tabulatation(cargos, K)
print(r)

아마 타뷸레이션을 풀 때 C언어를 배웠거나 파이썬으로 바로 시작하지 않는 사람들은

이처럼 표를 미리 작성해서 푸는 방식이 익숙할 것이다.

파이썬은 기본적으로 얕은 복사를 지원하기 때문에

열과 행을 통해서 2중 리스트를 만들고자 하는 경우는 매우 주의해야 한다.

 

나의 경우는 

pack = [0 for _ in range(capacity + 1)]
pack = [pack[:] for _ in range(len(cargos) + 1)]

이 부분에서 아래줄의 pack[:] 을 그냥 pack으로 적어서 한참을 헤맨 적이 있다.

pack[:]을 해 주지 않으면 깊은 복사를 하지 않기 때문에

i=n 일 때 반영한 결과가

i=n+1 일 때 반영할 결과에 영향을 줘서 값이 누적되는 현상이 발생한다.

 

파이썬으로 테이블을 만들 때는 이 부분을 항상 주의 하자.