[알고리즘] 무한 배낭 문제 (Unbounded Knapsack Problem)

1. 무한 배낭 문제

0／1 배낭 문제 가 각 물건이 1개씩 있고 배낭에 담느냐 안 담느냐를 선택하는 문제였다면 무한 배낭 문제는 각 물건이 무한히 이상 있는 경우 배낭의 물건의 가치가 최대가 되게 하는 문제다.

무한 배낭 문제는 0／1 배낭 문제와 유사한데 현재 물건을 담을지 말지 판단할 때 현재 물건을 이미 담았던 배낭을 통해 탐색하는 과정만 다르다.

---

2. 2차원 배열을 활용한 무한 배낭 문제

기존 0／1 배낭 문제를 2차원 배열을 활용한 다이나믹 프로그래밍으로 풀 경우 점화식은 아래와 같았다. 각 물건을 담을지 안 담을지 판단해서 배낭에 담긴 물건의 가치의 합이 최대가 되게 하는 경우다.

\[dp[i][j] = \begin{cases} dp[i-1][j], & j < w \\[6pt] \max \big(dp[i-1][j - w] + v,\ dp[i-1][j] \big), & j \ge w \end{cases}\]

여기서 배낭 용량이 부족해서 현재 물건을 담을 수 없는 경우인 $dp[i-1][j]$ 는 동일하다. 현재 물건을 애초에 담을 수 없으니 당연하다. 하지만 배낭 용량이 $w$ 보다 커서 현재 물건을 담을 수 있는 경우 기존에는 현재 물건을 담는 $dp[i-1][j - w] + v$ 와 현재 물건을 담지 않는 $dp[i-1][j]$ 를 모두 현재 물건의 이전 물건까지만 고려한 배낭을 통해 찾았다. 무한 배낭 문제의 경우 현재 물건을 몇 번이고 담을 수 있으므로 현재 물건을 담을 때 $dp[i][j - w] + v$ 로 현재 물건을 고려한 상황에서의 가치와 현재 물건을 담지 않은 경우인 $dp[i-1][j]$ 와의 비교를 통해 가치의 최댓값을 찾아야 한다.

최종 점화식은 아래와 같다.

\[dp[i][j] = \begin{cases} dp[i-1][j], & j < w \\[6pt] \max \big(dp[i][j - w] + v,\ dp[i-1][j] \big), & j \ge w \end{cases}\]

---

3. 1차원 배열을 활용한 무한 배낭 문제

역시 기존 0／1 배낭 문제를 1차원 배열을 활용한 다이나믹 프로그래밍으로 풀 경우와 유사하다. 기존 0／1 배낭 문제의 점화식은 아래와 같았다.

\[dp[i] = \max \big( dp[i - w] + v,\ dp[i] \big)\]

기존 0／1 배낭 문제는 역순 탐색을 통해 기존 물건을 담았던 배낭과 비교하는 논리 오류를 회피했는데 무한 배낭 문제의 경우 기존 물건을 또 담을 수 있으므로 오히려 정방향 탐색을 통해 담는 경우와 담지 않는 경우를 비교해야 한다. 탐색 방향만 다를 뿐 점화식 자체는 동일하다.

---