PostsSeriesLabsAlgo

DP

0/1 배낭

가방에 무엇을 담을까

가방은 5kg까지 담을 수 있습니다. 물건 A(무게 2 · 값 3), B(무게 3 · 값 4), C(무게 4 · 값 5) 중에서 무게의 합이 5를 넘지 않게 담아 값의 합을 가장 크게 만듭니다. 목표는 담을 수 있는 최대 가치입니다.

먼저 맞혀 보세요. 용량 5에 담을 수 있는 최대 가치는 얼마일까요?

가방 용량 →012345
물건 0개000000
A까지무게 2 · 값 30
B까지무게 3 · 값 40
C까지무게 4 · 값 50
채운 칸 0/15

내 예상 가치 0 · 실제 가치 0 → 달랐어요

0 → 0 → 3 → 4 → 5 → 7마지막 줄의 값입니다. 용량이 커질수록 담을 수 있는 최대 가치가 올라갑니다.

  • 칸의 값 — 안 담기(바로 위 칸)와 담기(무게만큼 왼쪽 위 칸 + 이 물건의 값) 중 더 큰 쪽
  • 끝 칸 — 용량 5에 담을 수 있는 최대 가치는 7이다
  • 무엇을 담았나 — 끝 칸에서 거꾸로 올라가며 위 칸과 값이 달라진 줄의 물건을 담은 것이다. 이 표에서는 A와 B이다

작은 가방부터 채워 큰 가방의 답까지 올라가는 표 = 0/1 배낭 (동적 계획법, DP). 0/1 은 물건마다 담거나 안 담거나 둘 중 하나라는 뜻입니다.

물건 30개 · 모든 경우 세기1,073,741,824가지
물건 30개 · 용량 1000 · 표 채우기30,000칸
담을지 말지 모든 경우를 하나씩 보면 컴퓨터로 약 2분 걸립니다. 표는 1초 안에 끝납니다.

물건마다 담거나 말거나 둘 중 하나다

  • 선택은 둘뿐 — 물건을 쪼개거나 두 번 담을 수 없다. 담으면 남은 용량이 물건의 무게만큼 줄어든다
  • 칸이 하나로 정해진다 — 앞 물건들과 남은 용량만 알면 그 칸의 답이 정해진다. ①에서 위 칸과 왼쪽 위 칸이 채워져야 눌렸던 이유다
  • 모든 경우를 세던 방법과 비교 — 완전탐색은 물건이 N 개면 2^N 가지를 본다. 표는 N × 용량 칸이다. 같은 칸의 답을 다시 구하지 않는다는 점은 메모이제이션, 앞 칸으로 채운다는 점은 1차원 DP와 같다

코드는 물건마다 용량을 한 줄씩 채우는 이중 반복문이다

물건과 용량은 ①과 같습니다. 다음을 눌러 한 줄씩 넘기며 노란 칸이 어떤 칸을 읽는지 보세요.

가방 용량 →012345
물건 0개000000
A까지무게 2 · 값 3000000
B까지무게 3 · 값 4000000
C까지무게 4 · 값 5000000

지금 채우는 칸 · 이 칸이 읽는 칸 (바로 위 칸 = 안 담기, 무게만큼 왼쪽 위 칸 = 담기) · 흐린 숫자는 아직 안 채운 칸

다음을 눌러 한 줄씩 넘겨 보세요

knapsack.py
  1. 1def knapsack(items, W):
  2. 2 n = len(items)
  3. 3 dp = [[0] * (W + 1) for _ in range(n + 1)]
  4. 4 for i in range(1, n + 1):
  5. 5 wt, val = items[i - 1]
  6. 6 for w in range(1, W + 1):
  7. 7 dp[i][w] = dp[i - 1][w]
  8. 8 if w >= wt:
  9. 9 dp[i][w] = max(dp[i][w], dp[i - 1][w - wt] + val)
  10. 10 return dp[n][W]
0 / 29
  • dp[i][w] = dp[i - 1][w] — 먼저 안 담은 값을 적는다. 바로 위 칸이다
  • if w >= wt — 무게가 용량보다 크면 담을 수 없어 위 칸 값 그대로 둔다
  • dp[i - 1][w - wt] + val — 담았을 때의 값이다. 무게만큼 왼쪽 위 칸에 이 물건의 값을 더한다

가방 용량을 6 으로 늘리면 담을 수 있는 최대 가치는 얼마일까요? 물건은 그대로 A·B·C 입니다.

그리디와 배열 줄이기에서 틀린다

  • 무게당 값이 큰 것부터 담으면 — 틀릴 수 있다. 용량 4에 P(무게 3 · 값 5), Q(무게 2 · 값 3), R(무게 2 · 값 3)이 있으면 P 부터 담아 5가 되지만 표는 Q 와 R 로 6을 찾는다. 이 장의 입력에서는 두 방법 모두 7이다
  • 1차원 배열로 줄일 때 — 용량을 큰 쪽부터 거꾸로 돌아야 한다. 앞에서부터 돌면 같은 물건을 여러 번 담아 용량 4 칸이 5가 아니라 6이 된다 (A 를 두 번 담은 값이다)
  • if w >= wt 를 빼면 — w - wt 가 음수가 되어 파이썬은 그 줄의 끝에서부터 칸을 읽는다. 에러 없이 이 입력의 답이 7이 아니라 12로 나온다
  • 0행과 0열 — 물건이 없거나 용량이 0 이면 값은 0 이다. 표를 0 으로 만들어 두면 이 칸들은 따로 채우지 않아도 된다

문제에서 이 말이 보이면

무게(용량) 제한이 있다최대 가치 · 최소 비용물건마다 담거나 말거나

다음 장에서는 큰 동전부터 주면 되는지를 따지는 거스름돈을 봅니다.