7 / 16강

넣을까 말까, 배낭 문제

가방이 허용하는 무게 안에서 물건의 가치 합을 최대화하려 합니다. 물건은 쪼갤 수 없으며, 각 물건은 한 번만 넣을 수 있습니다. 이것이 0/1 배낭 문제입니다. 0과 1은 각각 넣지 않거나 넣는 선택을 뜻합니다.

동전 문제와 달라지는 조건

동전 수업에서는 같은 종류를 여러 번 쓸 수 있었습니다. 이번에는 물건 하나를 두 번 쓰면 틀립니다. 상태를 앞의 i개 물건만 써서 용량 w에 담을 수 있는 최대 가치로 정하면 선택이 분명해집니다.

• 안 넣기: 앞의 i-1개 물건으로 같은 용량을 쓴 답입니다.
• 넣기: 현재 물건의 무게를 뺀 용량에 앞의 i-1개 물건을 담고, 현재 가치를 더합니다.
• 둘 중 큰 값을 고릅니다. 무게가 안 맞으면 안 넣는 선택만 가능합니다.

한 줄짜리 표로 줄이기

items = [(2, 5), (3, 7), (4, 9)]
capacity = 5
dp = [0] * (capacity + 1)
for weight, value in items:
    for space in range(capacity, weight - 1, -1):
        dp[space] = max(dp[space], dp[space - weight] + value)
print(dp[capacity])

물건은 (무게, 가치)이고 결과는 12입니다. 무게 2와 3을 골라 용량 5를 채웁니다. 아래에서 위로가 아니라 큰 용량부터 거꾸로 갱신해야 합니다. 그래야 dp[space-weight]가 아직 현재 물건을 반영하지 않은 값입니다.

예를 들어 무게 2인 물건 하나를 작은 용량부터 반영하면, 용량 2에 넣은 결과를 용량 4가 다시 읽어 같은 물건을 두 번 넣을 수 있습니다.

빠르다는 말의 범위

물건 수를 n, 정수 용량을 W라 하면 시간은 O(nW), 공간은 O(W)입니다. W가 커지면 비쌉니다. 컴퓨터에 W를 적는 데 필요한 자릿수는 훨씬 작기 때문에, 이 방법을 모든 입력에 대한 다항 시간 해법이라고 부르지는 않습니다. 이런 비용을 의사 다항 시간이라고 합니다.

물건을 쪼개도 되는 분할 가능 배낭 문제라면 단위 무게당 가치가 높은 순서의 탐욕법을 쓸 수 있습니다. 0/1 배낭과 조건이 다릅니다.

확인 문제

물건이 (2, 5) 하나이고 용량은 4입니다. 정답이 10이 나오면 어떤 규칙을 어긴 것일까요?