맨땅에 헤딩하면서 배운 배낭문제(Knapsack) 유형과 접근법 정리

배낭문제란?

배낭문제는 최대 k 무게를 싣을 수 있는 배낭에 n개의 아이템 을 넣어서 최대의 가치(아이템마다 가치가 다름) 를 만들어내는 문제입니다.
이 문제는 크게 두 가지 유형으로 나눠집니다.

1. 분할 가능한 문제 (Fractional)
대표적인 문제로는 오천원권 만원권 오만원권이 있을 때 목표 금액을 만들기 위해 최소의 수의 지폐를 사용하는 문제가 있습니다. 각 지폐는 더 작은 가치의 지폐로 나눠질 수 있습니다. 이 문제는 그리디 알고리즘 을 사용합니다.

2. 분할 불가능한 문제 (0/1)
이번 포스트에서 살펴볼 내용은 불할 불가능한 문제입니다. 현재 한국에서 사용하는 화폐 단위가 아니라 랜덤한 가치의 화폐가 주어지는 경우입니다. 예를들어 3만원권 7만원권 13만원권이 주어진다면 이는 분할 불가능한 문제 유형입니다. 그리고 이는 동적 계획법(Dynamic Programing) 으로 접근해야합니다.

기본적인 접근 방법

우선 아래의 문제의 첫 번째 테스트 케이스를 가지고 설명해보겠습니다.

백준 1535번 안녕

구분	값
가방의 무게 한도(k)	100
아이템의 개수(N)	3

구분	0	1	2
무게	1	21	79
가치	20	30	25

하위 문제로 나눠 점화식 세우기

NS(3, 100) = 1~3번 아이템을 가지고 100 무게를 사용해서 얻을 수 있는 가치의 최대값이라고 한다면,
하위 문제는 이렇게 나눌 수 있습니다. NS(2, 100 - 무게3) + 가치3 과 NS(2, 100)
즉, 3번째 아이템을 사용하는 경우와 사용하지 않는 경우로 나누는 것입니다. 각각의 문제는 다시 NS(1, 100 - 무게3 - 무게2) + 가치2 ...처럼 나눌 수 있습니다.

이를 점화식으로 일반화해서 표현하면 아래와 같습니다.
NS(k, n) = Max( NS(k - 무게n, n - 1) + 가치n, NS(k, n-1))

변수 설정하기

이를 구현하기 위해서는 위의 점화식에 표현된 n과 k를 무엇으로할 것이고, NS의 리턴값을 무엇으로 할지 정해야하고, 메모이제이션을 사용하기 위한 테이블을 정의해야합니다. 점화식에서처럼 n과 k, 두 개의 변수에 의해 값이 달라짐으로 2차원 배열로 정의하면 됩니다.

Bottom Up으로 해결하기

위의 점화식은 물론 재귀로 해결할 수도 있지만, 최종 결과 값을 도출하기 위해서는 각 재귀의 모든 스택이 끝나야만 함으로 StackOverFlow의 위험성이 상당히 큽니다. 따라서 Top Down 보다는 Bottom Up으로 해결하는 것이 효과적입니다.

이를 위한 수도 코드는 아래 처럼 구성할 수 있습니다.

Procedure nacksack(dp, weights, values):
for weight <- 1 to k do
    for i <- 1 to n do
        if i == 1 then
            dp[weight][i] <- 적절한 값
        else if weight - weights[i] < 0 then
            dp[weight][i] <- 적절한 값
        else if weight == weights[i] then
            dp[weight][i] <- 적절한 값
           else
            dp[weight][i] <- Max(dp[weight - weights[i]][i - 1] + values[i], dp[weight][i - 1])
        end if
    end for
end for 

return dp[k][n]

위처럼 Bottom Up으로 구성하면 이렇게도 생각해 볼 수도 있습니다. dp의 값은 weight를 구성하려고 하는데 아이템이 i ~ n번까지만 있을 때의 최대 가치 이고 아이템을 하나씩 추가하면서 최대값을 구하는 것입니다.

그리고 문제의 성격에 따라 위의 if 문에서 정의된 값을 적절히 넣어줘야합니다.

변형 유형

한 아이템을 두 번 이상 사용할 수 있는 경우

위의 예시에서는 아이템을 사용하거나 안하거나로 하위 문제를 나눴습니다. 그런데 아이템을 한번 이상 사용할 수 있다면 어떻게 될까요?

기존 점화식 NS(k, n) = Max( NS(k - 무게n, n - 1) + 가치n, NS(k, n-1))에서 아래와 같이 수정하면 됩니다.

NS(k, n) = Max( NS(k - 무게n, n) + 가치n, NS(k, n-1))

(k - 무게n)를 만들기 위해 n번 아이템까지 사용한 가치 + 가치n 를 사용하는 것입니다. 이렇게 수정하면 NS(k - 무게n, n)에서도 n번 아이템이 한번 사용된 경우가 고려되기 때문에, 결과적으로 n번 아이템을 0번~최대 까지 사용한 경우가 고려됩니다.

무게 한도 K를 무조건 넘기면서 가치의 최소값을 찾는 경우

이런 경우는 변수 설정을 잘 고려해야합니다. 보통 dp변수가 의미하는 값을 문제의 최종 리턴 값인 가치로 하게 되는데요. 그런데 이 경우에는 dp의 리턴 값을 가치 대신 무게로 설정할 수도 있습니다. 즉,

NS(v, n) => 가치 v를 만들기 위해 n번 아이템까지 고려했을 경우 무게의 최대값

NS(v, n) = Max( NS(v - 가치n, n-1) + 무게n, NS(v, n -1))
이고, NS의 값이 최초로 K를 넘어서는 시점의 가치를 리턴하면 됩니다.

소소한 팁

dp의 어느 축부터 순회할 지는 결과에 영향을 주지 않는다.

2차원 dp 배열을 1차원 dp배열로 축소하여 메모리 사용을 줄일 수 있다.

무게 / 아이템	0	1	2
1	1	21	79
2	20	30	25
2	..	...	...
100	~	~	~

위와 같은 dp 테이블이 있는 경우를 생각해보면, 사실 매번 dp테이블에서 n - 1열만 참조하고 있습니다. 따라서 이를 잘 활용하면 2차원 배열을 1차원 배열로 축소시킬 수 있습니다.
이를 위해서는
1. 아이템 축 -> 무게 축으로 탐색하도록 for문을 구성한다.
위의 예시에서 n-1열을 참조하기 때문에 n-1열은 무조건 채워져있어야하기 때문입니다.

2. 아이템을 0번 또는 1번 사용하는 경우에는 내부 순회 for 문(무게 축)을 뒤부터 순회해합니다.
위의 수도 코드를 다시보면,

`dp[weight][i] <- Max(dp[weight - weights[i]][i - 1] + values[i], dp[weight][i - 1])`

위에서 `dp[weight - weights[i]][i - 1]`에서 i - 1는 이전에 계산된 값이 때문에 일차원 배열로 옮겼을 때 이번 순회에서 수정되지 않은     을 참조하기 위해서 뒤부터 참조하는 것입니다.
반대로, 2번 이상 아이템을 사용하는 경우는 이번 순회에서 수정된 값을 참조해야하기 때문에 앞에서부터 순회해야합니다.

이상 이해하기 어려웠던 배낭문제를 여러 문제 다뤄보면서 정리해본 것이었습니다. 누군가에게 조금이라도 도움이 되면 좋겠습니다.