배낭 문제를 풀어내는 다양한 방법들! greedy, dp, backtracking, branch & bound

목차

knapsack 문제는 무게 제한이 있는 가방에,

무게 제한을 지키면서도 배낭에 담긴 물건의 가격의 합이 가장 큰 경우를 알아내는 문제이다.

 

이런 배낭 문제를 푸는 다양한 방법을 소개할 것이다.

1. 그리디한 방식과 그 한계
2. 일반적인 동적 계획법과 개선된 버전 
3. backtracking - dfs
4. 그리고 BFS를 이용한 분기 한정법 (dfs 보다 더 나을게 없다.)
5. 이를 개선한 Best First Search를 이용한 분기 한정법!

이렇게 5가지 방식을 소개할 것이다.

 

배낭에 적절한 무게 상한을 두는 것은 중요한 일이다

 

 

1. 배낭 문제와 그리디한 풀이

knapsack 문제는 배낭에 물건을 채우는 문제이다.

보통 물건들의 무게와 그 가격이 정해져 있는 상황이 주어지고, 최대 이득이 되는 만큼 물건을 채워야 하는 문제이다.
배낭은 감당할 수 있는 무게의 상한이 정해져 있기 때문에
정해진 무게 내에서 가장 가치의 총합이 높도록 배낭을 채우는 방법을 알아내는 문제이다.

문제 상황만 들어 봤을 때는 그리디하게 풀 수 있을것 처럼 보인다.
무게당 가치를 알아낸 다음 일종의 '가성비'를 이용해
가성비가 높은 물건 부터 채우면 되지 않는가?

만약 물건이 '쪼게어질 수 있다면' 이런 접근은 합리적이다.
배낭에 물건을 담을 때, 가방에 담을 수 있는 물건의 무게가 3kg 밖에 안 남았고
10kg이고 100만원짜리 물건과 3kg이고 500원짜리 물건이 남았을 때
10kg짜리 물건을 10분의 3으로 자를 수 있다면 정말 행복할 것이다.
그리디하게 풀 수 있다.

하지만, 보통은 물건을 쪼겔 수 없게 한다! (안 그러면 너무 쉽다)
예를 들어 30kg까지 담을 수 있는 배낭이 있고, 아래와 같이 3가지 물건이 있다.

1. 아이템1 : 50만원, 5kg
2. 아이템2 : 60만원, 10kg
3. 아이템3 : 140만원, 20kg

이 물건의 가성비를 계산해 정렬하면 1, 3, 2 순서로 정렬된다.

1. 아이템1 : 50 / 5 = 10만원
2. 아이템3 : 140 / 20 = 7만원
3. 아이템2 : 60 / 10 = 6만원

그래서 그리디한 풀이로 신나게 아이템 1, 3을 담으면 총 25kg가 담기고 190만원을 벌게 된다.
만약 물건을 쪼겔 수 있다면, 아이템 2를 반으로 잘라 배낭을 채워 220만원을 벌 수 있다.

하지만 일반적으로 배낭 문제는 보석을 훔치는 도둑,
군장을 싸는 군인과 같이 실제적인 상황의 문제로 주어지는데
이런 경우엔 물건을 쪼겔 수 없다.
닌텐도를 10분의 3으로 자른다거나 보조배터리를 반으로 자르고 가방에 넣으면 다 부숴질텐데 무슨 의미가 있는가

그래서 물건을 쪼겔 수 없다고 생각해보니,
아이템 1, 3을 남고 난 후의 배낭은 10kg만을 더 채울 수 있기 때문에
아이템 2를 추가로 채울 수 없고 알고리즘이 종료된다.

하지만, 아이템 2, 3을 고르면 30kg으로 담을 수 있고, 200만원을 벌게 된다!

이렇게 물건을 쪼겔 수 없다면 그리디한 풀이가 불가능한데,
물건을 쪼겔 수 없는 배낭 문제를 0-1 knapsack 문제라고 하고,
쪼겔 수 있는 문제를 배낭 빈틈없이 채우기 문제라고 한다. (채우거나 말거나여서 0-1 문제인듯 하다)

 

2. 동적 계획법 풀이

0-1 kanpsack 문제는 동적 계획법으로 풀 수 있다.

물건의 갯수와 무게를 기준으로 풀어나갈 수 있다.

예를 들어 i개의 물건을 w라는 제한만큼 채운다면 아래와 같은 표현이 가능하겠다.

P[i][w]

dp 배열 P가 있고, 0번 물건에서 i번까지의 물건들 중

무게 w까지의 제한을 두었을 때 얻을 수 있는 최대 이익이 P[i][w]이다.

물건이 n개이고, 배낭의 제한이 W라면 P[0][0]에서 시작해 P[n][W]를 구하면 되는 것이다!

이제 일반식을 보자 (recursive property)

 

 

초기값은 P[0][w] = P[i][0] = 0으로 두고,

위 식을 반복해 P[n][W]까지 계속해서 만들어 내면 되는 것이다.

각 반복에서 i번째 물건의 무게를 무게 제한에서 뺐을 때, 그 값이 0보다 크다면 위쪽의 max가 포함된 수식을 적용한다.
왜 기준이 w_i이 w보다 작은가 큰가일까?
단순하다. "채울 수 있어서"다. 만약 무게 제한보다 물건 i의 무게가 더 크다면 채울 수 없다.
이걸 괜히 어렵게 "w_i <= w인 경우"로 표현한 것이다.

 

만약 i번째 물건을 담을 수 없는 경우 당연히 이번 물건을 제외한 0 ~ i-1 번째 물건까지 채운 케이스 중
최적의 케이스를 선택하는 것이 옳고,
i번째 물건을 채우는 것이 더 이득이라면 p_i + P[i - 1][w - w_i]로 값을 갱신 한다.

동적 계획법 개선

위 알고리즘은 어느 정도 좋아 보이지만, n * W의 복잡도를 갖는다.

각 i에 대해 w를 지정할 때 0 ~ w의 모든 제한을 계산하고 있다.
굳이 w까지 계산할 필요 없이 0 ~ i번째 물건까지의 무게 합까지만 계산하는 방식으로 이를 줄일 수 있지만,
더 줄일 수도 있다.

물건을 어차피 쪼겔 수 없다면, 계산에 필요한 무게는 정해져 있다.

 

무슨 말인지 예를 들어보겠다.
예를 들어 모든 물건의 무게의 1의 자리가 5로 끝난다면 일의 자리가 1 ~ 4, 6 ~ 9인 w는 계산할 필요도 없다.

이런 식으로 사실 0 부터 w까지 모두 체크할 필요가 없는데,

탑-다운 방식으로 개선하면 계산 가능하다.

 

위는 P[n][W]를 구하는 마지막 식인데, 사실 필요한 엔트리는 P[n-1][W], P[n-1][W - w_n] 2개 뿐이다.

n에서 부터 아래로 내려오면 계산할 필요 없는 엔트리를 정리할 수 있고,
i번째 행에 어떤 엔트리가 필요한지 결정한 다음 (i-1)째 행에 필요한 엔트리를 결정 가능하다.

 

결국 P[i][w]를 계산할 땐, 아래 두 식을 가지고 계산하면 된다.

 

 

이러한 풀이는 2^n의 연산 횟수를 가진다.

실제로 백준에서 골드급의 배낭문제를 풀 때는 이정도의 복잡도로 처리가 가능하다.
너무 오래되서 잘 기억나지 않지만 플레티넘급의 백준 문제를 풀이할 때는 시간복잡도 문제로 풀지 못 했었다.
아마 개선된 버전으로 풀어야 했었을 것 같다. 다시 풀어봐야겠다.

 

3. backtracking - dfs

배낭 풀이 문제를 백트래킹으로 풀 수도 있다.

트리를 그릴 것이다.

 

backtracking으로 만든 상태공간트리 (dfs)

 

 

각 depth마다 아이템을 하나 갖는다.

아이템을 배치한 순서는 '가성비'이다. 값을 무게로 나누어 무게당 값이 높은 것 부터 위에 배치한다.

그렇게 아이템 1 ~ 4를 위에서 부터 아래로 배치한다.

 

각 노드에서 왼쪽 간선으로 뻗어 나가는건 그 depth번째의 물건을 담는다는 것을,
오른쪽 간선 쪽은 담지 않는다는 것을 의미한다.

각 노드는 price와 weight를 갖는다.
그리고 bound라는 값을 갖는데, 해당 노드에서 계속 뻗어 나갈 때 얻을 수 있는 최대 이득이다.
bound의 계산은 그리디하게, 빈틈없이 채운다.

그러니까 아래로 내려가면서 채울 수 있는 만큼 모두 채운 다음,
마지막엔 남은 무게만큼 물건을 잘라 채운다.

그리고 전역적으로 최대 값인 maxPrice 변수를 갖는다.

이 maxPrice는 최고 price를 갖는 노드를 만날 때마다 갱신된다.
어떤 bound를 계산했을 때, maxPrice보다 작다면 그 노드의 자식노드들은 탐색 하나 마나 max가 될 수 없다.
물론 depth번째 물건을 담는 경우 배낭 무게 상한을 초과하면 그 노드도 더는 탐색하지 않아도 된다.
이 두 상황을 유망하지 않다 라고 표현하며, 유망한 노드만 탐색을 이어 나갈 것이다.

여기선 dfs방식으로 트리를 그려나갈 것이다.
따라서, C++ 코드는 아래와 같이 구현된다.

 

가독성에만 중심을 두어 코드가 난잡하다. (그런것 치고 변수명은 불친절하다)

재귀적으로 수행되면, promising이 true인 경우 -> 유망한 경우

include라는 아이템 포함을 나타내는 배열에 i + 1번째 아이템을 담았음을 알리고 (include[depth+ 1] = true)

depth+1번째 아이템을 담았다고 표시하며 (profit과 weight를 더해주며) 왼쪽으로 뻗어 나간다.

 

재귀적으로 수행되므로, include에서 아이템 번호를 빼고 오른쪽으로 진행한다.

 

promising은 아래와 같다.

promising은 노드가 유망한지 검사한다.

일단 i번째 물건을 더한 무게가 무게 상한 W보다 크다면 바로 false를 반환한다.

그게 아니라면, 다음번 물건 부터 greedy하게 모두 채운다. 

채울 수 있을 만큼 채운 다음 마지막 물건은 쪼게어서 빈틈없이 채운다. 

이것이 이 노드를 계속 탐색했을 때 얻을 수 있는 최대 이익이다.

이 값이 maxProfit 즉, 이제까지 찾은 price 중 최대값 보다 작거나 같다면 탐색하나 마나일 것이다. 

따라서 return값으로 bound > maxProfit을 사용했다.

 

 

4. BFS를 이용한 Branch & Bound

BFS를 이용한 분기 한정 방식 탐색이다.

사실 dfs를 이용한 이전의 방법 보다 더 나을게 없지만, Best First Search를 보여주기 위한 발판이다.

일반적인 BFS 탐색과 같이 Queue에 자식 노드를 넣어가며 탐색을 진행한다.

 

먼저 간단히 설명하자면, DFS때와 같은 노드를 이용한 트리를 그릴 것이다.

다만 Queue를 이용하는 것이다.

 

괜히 코드도 보여주기 전에 초 치는것 같지만,

사실 DFS로 탐색함은.가성비가 좋은 물건을 "담은"케이스를 먼저 살펴보면서

maxProfit을 적절하게 갱신할 수 있었고, 그 덕분에 많은 경우들을 고려하지 않아도 됐다.

하지만 BFS를 사용하는 경우 i번째 물건을 넣을때/안 넣을때를 모두 한번에 조사하므로 더 많은 case를 들여다볼 가능성이 더 높다.

 

BFS + 분기한정법

 

이전의 DFS 때와 비교해보면 확실히 주어진 예시의 경우 더 많은 노드를 방문하는 것을 확인할 수 있다.

 

코드를 보고 빠르게 넘어가자.

진행은 일반적인 BFS처럼 진행된다. 각 노드에서 자식 노드들을 전부 Queue에 담는 것이다.

Node는 레벨(depth), profit, weifht를 가지고 있따.

 

getBound 메서드를 이용해서 자식 노드의 Bound값이 현재 maxProfit 보다 높으면 탐색을 진행한다.

왼쪽의 경우 weight와 profit을 더한 leftNode를 만들고, 오른쪽의 경우 level만 다른 노드 rightNode를 넣는다.

 

getBound는 아래와 같이 생겼다.

사실 DFS에서 Bound를 계산했던 방식과 아예 똑같다.

 

 

profit을 bound 초기 값으로 잡고, 더할 수 있을 만큼 더합니다.

이후 똑같이 max값과 비교합니다 (사실 여기에도 isPromising 메서드를 만드는게 더욱 깔끔할것 같다.) 

 

5. Best First Search를 이용한 Branch & Bound!

코드를 먼저 보여주겠다.

 

사실싱 BFS를 사용한 버전과 코드가 거의 동일하다.

똑같이 "다 해본다" 그러면서

 

1. 용량이 최대 용량보다 커지거나,

2. Bound를 계산했는데, 이전에 더 큰 Profit을 발견한 적이 있다.

 

라면, 탐색하지 않는다.

다만, Queue 대신 Bound가 높은 순서로 노드를 정렬한 Priority Queue를 사용한다는 점만 다르다. 

 

해보면 아래와 같은 그림이 나온다

Best First Search로 그린 트리

Bound는 그 노드에서 뻗어 나갔을 때 얻을 수 있는 Profit의 한계치이다.

따라서, Bound가 높은 노드를 먼저 탐색하는 방식은 유망하면 유망할 수록 먼저 살펴보겠다는 의미이다.

 

따라서 루트 노드에서 bound를 115로 평가한 다음 (1, 1), (1, 2) 두 자식을 만들어낸다.

이후 PQ에 의해 (1, 1)을 탐색하게 된다. (2, 1)과 (2, 2)에 대한 계산을 마치고 PQ에 넣는다면,

(1, 2) 대신에 (2, 1)이 먼저 평가될 것이다.

 

(2, 1)에서 뻗어나온 두 노드를 보면, 하나는 무게 제한을 벗어났다. 그 경우 bound를 0으로 두는게 좋다.

이후 PQ에 의해 (1, 2) 보다도 (2, 2)를 먼저 탐색하게 된다. 

 

(3, 3), (3, 4)를 계산하고 90$로 초기화 되며 maxProfit을 찾게 된다.

이후 남은 노드들은 전부 탐색되지 않는데 bound가 90$ 보다도 작기 때문이다.

BFS보다 연산량도 많이 줄었고 과정 자체가 너무 깔끔하다.

 

단순히 제시된 예시만 보면

DFS는 13개, BFS는 17개

그리고 Best First Search는 11개 노드를 검사했다.

 

이는 적은 차이처럼 보이지만, 트리가 커지면서 차이는 매우 커질것이다.

 

정리해보면

빈틈없이 채우는 배낭 문제는 그리디로 풀 수 있었고,

0-1 배낭 문제는 풀 수 없었다.

 

그래서 대안으로 동적 계획법을 시도할 수 있었는데, 아래서 위로 올라가는  n*W 연산 횟수의 방식과

위에서 아래로 내려가는 2^n 연산 횟수의 개선된 방식을 살펴봤다.

 

그리고 분기를 한정시키는 방법을 살펴봤는데,

기본적으로 bound라는 해당 노드에서 얻을 수 있는, 최대 이득을 계산한 변수를 가진 노드를 사용했다.

DFS, BFS, Best First Search 방식을 살펴봤는데,

제일 괜찮은건 높은 Bound 부터 처리하는 Best First Search 방식을 이용하는 것이였다.

 

Reference

• Foundation Of Algorithms <Richard Neapolitan>