Knapsack

2020-1학기, 대학에서 ‘알고리즘’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

ps) “knapsack”의 뜻은 “하이킹 따위의 아주 간단한 스포츠에 사용되는 작은 륙색”이라고 한다. 이곳에 륙색에 대해 잘 설명이 되어 있으니, 궁금한 사람은 한번 읽어보자 😁

---

도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은?

위와 같이 <냅색; knapsack> 문제는 유한한 최대 용량, Capacity 아래에서 담긴 값의 합이 최대가 되도록 하는 최적화 문제다. 냅색 문제의 경우, 배낭에 넣는 대상이 (1) pick w/ replacement (2) pick w/o replace (3) 대상을 자를 수 있는지(fractional knapsack)에 따라서 알고리즘이 조금씩 달라진다. (1), (2)번 경우는 DP를 통해 해결하고, (3)번의 fractional knapsack은 $v_i / w_i$의 ratio를 이용해 Greedy로 해결한다💪

---

Pick w/ replacement

첫번째 경우는 아이템의 수가 무한히 많은(unlimited quantities) 경우를 말한다. 이때, 냅색 문제는 capacity를 1부터 올려가며 이전에 계산한 냅색 DP의 값에 아이템을 추가했을 때, 가장 큰 value를 유도하는 조합을 찾는 문제가 된다. 일단 코드를 살펴보자!!

Initialize all $K(j) = 0$.

for $w=1$ to $W$
  $\displaystyle K(w) = \max_{1\le i\le n} \{ K(w - w_i) + v_i : w - w_i \ge 0 \}$

return $K(W)$

정말 간단하다!!!

---

Pick w/o replacement

두번째 경우는, 배낭에 담을 수 있는 아이템의 수가 오직 하나만 있는(only one of each item available) 경우를 말한다.

이 문제를 풀기 위해선 아이템을 고를지 말지로 sub-problem을 생성하는 binary choice의 방식으로 접근해야 한다.¹ 그래서 전체 $1$부터 $n$개의 아이템 중에서 $j$-th 아이템까지 사용해 냅색 문제를 풀고, 그 결과를 $(j+1)$-th 아이템을 추가한 경우를 풀때 활용하는 방식으로 접근해야 한다.

이때, $j$-th 아이템을 추가할 때, 몇가지 선택지가 있는데,

1. 만약 현재 살펴보는 capacity $w$가 $j$-th 아이템의 무게보다 크다면, 아이템을 추가하지 못하기 때문에 $j$-th 아이템을 추가하기 직전의 냅색 solution을 그대로 사용한다. 따라서,

\[\text{if} \quad w_j > w \; \text{,} \quad \text{then} \quad K(w, j) = K(w, j-1)\]

2. 만약 현재 $j$-th 아이템의 무게를 넣을 수 있는 경우($w - w_j \ge 0$)라면, (1) $j$-th 아이템을 담지 않는 경우 (2) $j$-th 아이템을 담는 경우에서의 가치를 비교해 더 큰 것을 취한다.

\[\text{if} \quad w \ge w_j \; \text{,} \quad \text{then} \quad K(w, j) = \max \{ K(w, j-1), K(w-w_j, j-1) \}\]

위의 알고리즘을 코드로 옮기는 것은 결국 2차원 DP 문제를 푸는 것과 같다! 코드를 살펴보자!

Initialize all $K(0, j) = 0$ and all $K(w, 0) = 0$.

for $j=1$ to $n$
  for $w=1$ to $W$
    if $w_j > w$
      $K(w, j) = K(w, j-1)$
    else
      $\displaystyle K(w, j) = \max \{ K(w, j-1), K(w-w_j, j-1) + v_j\}$

return $K(W, n)$

2차원 DP의 모습을 그려보면 요런 느낌으로 DP 배열이 채워진다

---

본인의 PS 경험상, 냅색 문제임을 명확히 알 수 있는 문제를 푸는 건 어렵지 않다. 하지만, 냅색 문제인지 전혀 모르겠는데, 사실은 냅색으로 풀어야 되는 문제들이 종종 있다. 예를 들면 2019 ICPC 한국 예선 1번 문제인 17528번: Two Machines가 냅색인지 판단하는게 쉽지 않은 그런 문제였다.

---

추천 문제

• 12865번: 평범한 배낭
• 1450번: 냅색문제 ← 평범한 냅색 문제처럼 보이지만, 꽤 Hard 하다 🤖
• 12920번: 평범한 배낭2 ← 약간의 변형과 함께, 분할 정복 테크닉을 하나 더 써야 하는 문제다 😺
• 냅색 카테고리의 문제 모음

참고자료

• “메시에”님의 포스트

---

1. 또다른 DP 문제인 Weighted Interval Scheduling에서도 binary choice 기법을 사용했었다! ↩