[알고리즘 - 이론] 0-1 KnapSack Problem and Fractional KnapSack Problem (0-1 배낭 문제, 분할 가능한 배낭 문제)

 

---

앞의 글을 읽으시면 이해에 도움이 됩니다.

 

2022.04.16 - [Computer Science/알고리즘] - [알고리즘] 탐욕법이란? (What is the Greedy Approach?)

[알고리즘] 탐욕법이란? (What is the Greedy Approach?)

2022.04.13 - [Computer Science/알고리즘] - [알고리즘] 동적 계획법 (Dynamic Programming)

[알고리즘] 동적 계획법 (Dynamic Programming)

2022.05.26 - [Computer Science/알고리즘] - [알고리즘 - 이론] The BackTracking Algorithm (되추적 알고리즘)

[알고리즘 - 이론] The BackTracking Algorithm (되추적 알고리즘)

2022.05.27 - [Computer Science/알고리즘] - [알고리즘 - 이론] Branch-and-Bound Strategy (분기한정법)

[알고리즘 - 이론] Branch-and-Bound Strategy (분기한정법)

---

1. 0-1 KnapSack Problem이란?

 

 

도둑이 배낭을 메고 보석 가게에 들어왔다.

훔친 보석의 총 무게가 배낭의 용량 W를 초과하면 배낭이 찢어진다.

각 보석의 무게와 값어치는 알고 있다.

이때 밤손님의 딜레마는 훔친 보석의 총무게가 W를 넘지 않으면서도, 보석의 총 값어치가 최대가 되도록 하는 보석을 배낭에 담는 것이다.

 

 

이때 보석을 자를 수 있는 문제인 Fractional KnapSack Problem와 보석을 자를 수 없는 문제인 0-1 KnapSack Problem이 있다.

보통 0-1 KnapSack Problem이 주로 다뤄진다.

 

이때 무게나 값어치를 기준으로 계산하면 최적의 해답을 얻을 수 없으므로, 무게 당 이익을 기준으로 계산해야 합니다.

(하지만 DP, Enhanced DP에서는 아님)

 

이제 해당 문제를 푸는 알고리즘 기법들에 대해 소개하겠습니다.

 

아래는 KnapSack Problem을 해결하는 기법과 코드가 있는 주소입니다.

최근에 작성한 코드일수록 주석 처리가 깔끔하고, 더 효율적입니다.

• Fractional KnapSack Problem
  • Greedy Approach
    • https://hi-guten-tag.tistory.com/100
• 0-1 KnapSack Problem
  • Dynamic Programming
  • Enhanced Dynamic Programming
    • https://hi-guten-tag.tistory.com/119
  • Back Tracking
    • https://hi-guten-tag.tistory.com/120
  • Branch and Bound
    • https://hi-guten-tag.tistory.com/139

---

2. Fractional KnapSack Problem (분할 가능한 배낭 문제)

 

2.1 Greedy Approach (탐욕법)

 

탐욕법을 사용하면 항상 최적의 해답을 얻을 수 있습니다.

무게 당 이익이 높은 보석을 기준으로 먼저 넣으면 끝입니다.

 

예를 들어

아이템 1 : 50만 원, 5KG

아이템 2 : 60만 원, 10KG

아이템 3 : 140만 원, 20KG이 있다고 가정하자.

배낭에 담을 수 있는 총 무게는 30KG이다.

 

이때 무게 당 이익을 나타내면,

아이템 1 : 50/5 = 10만 원

아이템 2 : 60/10 : 6만 원

아이템 3 : 140/20 : 7만 원이 되므로, 무게 당 이익이 큰 것부터 나열하면 아이템 1, 아이템 3, 아이템 2가 됩니다.

 

따라서 배낭에는 아이템 1, 아이템 3을 넣고, 아이템 2를 5KG만 넣으면 최적의 해답이 나옵니다.

 

따라서 greedy approach로 fractional knapsack problem은 항상 최적의 해답을 얻게 됩니다.

---

3. 0-1 KnapSack Problem (0-1 배낭 문제)

 

 

2.1 Greedy Approach (탐욕법)

 

 

참고로 탐욕법으로 0-1 배낭 문제를 풀 수 없습니다.

위의 아이템 예시를 들겠습니다.

총 무게는 30KG이므로, 아이템 2와 3을 넣으면 200만 원의 이익이 생깁니다.

 

하지만 탐욕법을 사용해서 문제를 해결한다면, 아이템 1과 3을 넣어서 190만 원의 이득밖에 못 챙깁니다.

 

더 복잡한 탐욕 알고리즘을 사용하더라도 0-1 배낭 문제를 풀 수 없습니다.

---

2.2 Dynamic Programming (동적 계획법)

 

 

우선 DP로 문제를 풀기 위해서는 최적의 원칙이 적용된다고 증명해야 합니다.

 

만약 A를 n개의 아이템 중에서 최적을 이루는 부분집합이라고 가정합니다.

이때 A가 아이템 n을 포함하는 경우와 포함하지 않는 경우 두 가지로 나눌 수 있습니다.

 

만약 아이템 n을 포함하지 않는다면, A는 n-1개 아이템들 중에서  최적을 이루는 부분집합과 같습니다.

만약 아이템 n을 포함한다면 A에 속한 아이템들의 총 무게는 W - w_n을 초과하지 않는다는 조건 하에 n - 1개의 아이템들을 선택하여 얻는 최적의 이익에다가  p_n을 더한 것과 같습니다.

 

따라서 최적의 원칙이 적용됩니다.

 

 

이제 문제를 일반화할 수 있습니다.

i > 0과 w > 0인 경우 총 무게가 w를 초과할 수 없다는 제약조건 하에서 처음 i개 아이템에서만 선택할 때 얻는 최적의 이익을 P[i][w]라고 하면, 다음과 같은 식을 얻을 수 있습니다.

\(P[i][w]=\left\{\begin{matrix}
maximum(P[i-1][w], p_i + P[i-1][w-w_i]) & w_i \leq w\\
P[i-1][w] & w_i > w \\
\end{matrix}\right.\)

즉 아이템을 넣을 수 있다면, 넣지 않았을 때와 넣었을 때를 비교해서 maximum 값을 넣으면 되고,

아이템을 넣을 수 없다면, 바로 이전의 값을 가져오면 됩니다.

이때 최대 이익은 p[n][W]와 같습니다.

 

Base condition은 P[0][w] = 0, P[i][0] = 0으로 두면 됩니다.

 

def kanpsack(P: list):
    for i in range(n + 1):
        P[i][0] = 0
    for j in range(1, W + 1):
        P[0][j] = 0

    for i in range(1, n + 1):
        for j in range(1, W + 1):
            P[i][j] = P[i - 1][j] if w[i] > j else P[i][j] = max(P[i-1][j], p[i] + P[i - 1][j - w[i]])

 

근데 만약에 모든 아이템의 무게의 합이 100인데, 배낭의 용량이 100억이라면 어떻게 될까요?

아마 쓸데없는 계산까지 하게 될 겁니다.

 

즉 아이템의 수와 배낭의 무게는 아무런 상관관계가 없으며, 계산은 \(\Theta (nW)\)번 하게 됩니다.

만약에 W가 n! 이라면? nW는 \(\Theta(n!)\)에 속하게 되고, W가 2의 거듭제곱 형태라면 nW는 2의 거듭제곱 형태로 나타납니다.

이 말은 결국 Brute-Force Algorithm이 더 좋을 때가 종종 있다는 뜻입니다.

 

따라서 DP를 개선해야 할 필요성이 있습니다.

---

2.3 Enhanced Dynamic Programming (개선된 동적 계획법)

 

 

위의 DP는 W가 매우 클 때, 쓸데없는 계산까지 하는 DP입니다.

이를 개선한 DP를 소개하겠습니다

 

P[n][W]를 보면 정작 필요한 값은 P[n-1][W], P[n-1][W-w_n]이 전부입니다.

따라서 P[3][30]을 구하고 싶으면 P[3-1][30]과 P[3-1][30 - w_n]만 있으면 됩니다.

 

따라서 n에서부터 뒤로 이 작업을 계속하면 계산할 필요가 있는 엔트리만 결정할 수 있습니다.

만약 n = 1이거나 w <= 0이라면 이 작업을 멈추면 됩니다.

 

따라서 최악의 경우에 개선된 DP가 얼마나 효율적인지 계산해보겠습니다.

n일 때 n - 1행의 두 개의 엔트리를 한 번 비교하므로 1번 계산

n -1일 때 n - 2행의 두 개의 엔트리를 두 번 비교하므로 2번 계산

...

2일 때는 1행의 두 개의 엔트리를 2^(n-2)번 비교하므로 2^(n-2)번 계산

1일 때는 본인의 엔트리를 2^(n - 1)번 비교하므로 2^(n - 1)번 계산

(n = k일 때, 비교는 2^(n - (k))

따라서 계산하는 엔트리의 개수는 1 + 2 + ... + 2^(n-1) = 2^n - 1이 됩니다.

이는 결국 \(\Theta(2^n)\)이 됩니다.

 

이때 n과 W로 계산하는 엔트리의 개수를 표현하면, 이 또한 \(\Theta(nW)\)가 됩니다.

 

따라서 최악의 경우 계산하는 엔트리의 총 개수는 \(O(minimum(2^n, nW))\)가 됩니다.

 

만약 DP로 풀 때, 최악의 경우가 2^n이라고 하면 틀린 말입니다. nW가 더 큰 값이 될 수도 있기 때문에 이는 정답이 아닙니다.

 

 

 

+ 공간 복잡도까지 개선한 알고리즘 (Hash Table 사용)

 

만약에 Hash Table을 사용한다면, 따로 nW 크기의 배열을 만들 필요가 없습니다.

이때 최악의 경우 공간 복잡도는 \(O(minimum(2^n, nW))\)이 됩니다.

Hash Table의 key는 n,w 값으로 이루어져 있기 때문입니다.

---

2.4 Back Tracking (백 트래킹)

 

 

이 문제는 Sum of Subset처럼 넣으면 왼쪽, 빼면 오른쪽으로 가면 끝입니다.

하지만 0-1 배낭 문제는 일반 다른 백트래킹 문제와는 다르게 최적화 문제입니다.

따라서 경로를 찾았다고 해서, 그대로 끝나는 것이 아니라 검색이 완전히 끝날 때까지 탐색을 해야 합니다.

만약 특정 마디까지 넣은 아이템이 지금까지의 최고 해답보다 값어치가 크다면 지금까지의 최고 해답의 값을 바꿔야 합니다.

 

따라서 우리는 유망한 마디의 자식들을 모두 방문해야 합니다.

 

아래는 일반적으로 최적화 문제의 경우에 백 트래킹 알고리즘입니다.

def checknode(node v):
	if value(v) is better than best:
    	best = value(v)
    if promising(v):
    	for each child u of v:
        	checknode(u)

 

이제 마디가 유망하지 않은 경우에 대해 생각하면, 배낭에 더 이상 아이템을 넣을 공간이 남아있지 않은 경우가 있습니다.

따라서 어떤 마디까지 넣은 weight가 W보다 크다면 그 마디는 더 이상 유망하지 않습니다.

 

이때 최적화 문제의 경우 '유망'이란 자식 마디로 더 팽창해야 하므로, weight == W인 경우조차 유망하지 않습니다.

 

또한 추가적으로 그 마디의 자식을 모두 담았음에도 불구하고,

지금까지 찾은 최대 값어치보다 작다면 그 마디 또한 유망하지 않습니다.

 

0-1 배낭 문제이지만, 보석을 쪼개서 최대한 꽉꽉 채워 넣어서 그 마디에서 얻을 수 있는 값의 상한선을 얻어도, 최고 해답보다 작다면 아무 의미 없기 때문입니다. (물론 값의 상한선을 얻을 수는 없음)

 

따라서 해당 수식이 성립하면 유망하지 않습니다.

(i번째 깊이까지 갔고, k번째 깊이에 있는 마디는 무게의 합이 W가 넘어가는 마디)

\(totweight = weight + \sum_{j = i + 1}^{k - 1}w_j\)

\(bound = (profit + \sum_{j = i + 1}^{k - 1}p_j) + (W - totweight)*\frac{p_k}{w_k}\)

\(bound \leq maxprofit\)

 

즉 k - 1번째까지 모두 더하고, k번째 마디에 있는 아이템을 쪼개서 넣었음에도 불구하고, 지금까지의 최고 해답인 maxprofit보다 작다면 유망하지 않습니다.

 

참고로 보석을 최대한 꽉꽉 채워 넣은 bound를 얻기 위해서는 해당 아이템들이 무게당 이익으로 정렬되어 있어야 합니다.

 

 

직접 그려보면 알겠지만, 실제로 Back Tracking이 몇 개의 마디를 검사하는지는 알 수 없습니다.

Enhanced DP에서는 최악의 경우 \(O(minimum(2^n, nW))\)개의 엔트리를 검사하고,

Back Tracking에서는 최악의 경우 \(\Theta(2^n)\)개의 마디를 검사합니다.

 

언뜻 보기에 DP가 더 효율적인 것 같지만, Back Tracking은 고려해야 할 사항이 너무 많아서 두 개의 알고리즘의 상대적인 효율을 이론적으로 분석할 수 었습니다.

 

이럴 때는 많은 난수를 가지고 알고리즘을 직접 실행해 보고, 어떤 알고리즘이 더 좋은지 알아봐야 알 수 있습니다.

1974년에 이 실험을 했는데, Back Tracking이 DP보다 보통 더 효율적임을 알아냈다고 하네요.

뭐.. 그렇대요

 

참고로 maxprofit을 업데이트하는 과정과 유망한 지 체크하는 과정은 엄연히 다른 과정임을 명심해야 한다..!

---

2.5 Branch and Bound (분기 한정법)

 

 

BFS로 방문하는 방법이 있고, Best-first search로 방문하는 방법이 있습니다.

여기서는 best first search에 대한 방법을 쓰겠습니다.

 

0-1 KnapSack Problem에서 분기한정법은 Back Tracking과 매우 흡사합니다.

다만 차이점은

• 트리 횡단 방법에 구애받지 않고, 최적화 문제에 사용된다.
• bound 값이 큰 마디를 먼저 방문한다.
  • 즉 제일 유망해 보이는 마디를 먼저 방문한다는 뜻
• promising 함수는 bool을 반환하는 것이 아닌 해당 마디에서의 bound를 반환한다.
• 만약 어떤 마디의 bound 값이 지금까지 얻은 maxprofit보다 작으면 더 이상 마디를 방문하지 않는다.

가 되겠습니다.

 

즉 되추적에서는 DFS로 마디를 방문했다면, 분기한정법에서는 Best First Search 기법을 사용하여 마디를 방문합니다.

 

따라서 Priority Queue를 사용하여 Bound 값이 높은 노드를 우선적으로 빼야 하고, 이를 바탕으로 더 유망한 노드를 먼저 갑니다.

이때 Bound 값이 높은 노드를 우선적으로 뺐는데, 지금까지 얻은 maxprofit보다 작다면 더 이상 방문하지 않습니다.

(이때의 노드는 maxprofit이 업데이트되기 전에 들어간 노드)

 

 

특정 예시)

dfs (back tracking)으로 문제를 푼다면 13개의 노드를 방문하고,

bfs (branch and bound)으로 문제를 푼다면 17개를 방문하지만,

best first search로 문제를 푼다면 11개의 노드를 방문합니다.

 

 

 

 

 

이상입니다....

 

감사합니다.

 

 

지적 환영합니다.