-
0-1 Knapsack Problem대학/알고리즘 2023. 6. 10. 20:50
0-1 Knapsack Promble은 각각의 가치(profit)와 무게(weight)를 갖는 여러 아이템을 가방에 추가하는데,
최대 가방이 담을 수 있는 무게를 초과하지 않는 범위에서
아이템의 가치가 최대가 되도록하는 아이템의 집합을 찾는 알고리즘이다.
이 문제를 접근하는 방법은 여러개가 있어 한 번에 소개해보고자 한다.
Greedy Approach
그리디한 방법으로 해결하는 접근방식은 다음과 같다.
단위무게당 가격으로 내림차순 정렬을 하고, 무게가 가득 찰 때 까지 집어넣는 방식이다.
하지만 이 방식에는 문제가 존재한다.
바로 항상 최적해를 도출하지는 못한다는 것이다.
단, fractional knapsack problem의 경우에는 그리디한 방법으로도 최적해를 도출할 수 있다.
(fractional: 아이템 하나를 다 넣거나 넣지 않는 것이 아닌, 0.3아이템과 같이 일부만 담을 수 있는 문제)
0-1 knapsack은 최적해를 도출하지 못하기에, fractional knapsack problem의 시간 복잡도를 구해보면,
시간 복잡도는 정렬시 MergeSort를 사용한다 했을 때 Θ(n lg n)의 시간 복잡도를 갖는다.
(Greedy 과정은 n번만 탐색하면 끝남)
Dynamic Programming
동적 프로그래밍 방식으로 해결하는 접근 방식은 다음과 같다.
$$ P[i][w] = \left\{\begin{matrix}
max(P[i-1][w], \; p_i+P[i-1][w-w_i]) \; (if \; w_i \leq w) \\ P[i-1][w] \; (if \; w_i > w)
\end{matrix}\right. $$P[i][w]: 정렬된 아이템 중, 처음부터 i개의 아이템을 넣을 것인지, 넣지 않을 것인지 선택해서
아이템을 골랐을 때, 무게 w를 넘지 않을 때의 최적해를 저장.따라서 아래의 케이스는 아이템 i의 무게 wi가 현재 가방에 더 넣을 수 있는 무게 w보다 커서 가방에 넣을 수 없는 상태이고,
위의 케이스는 아이템 i의 무게 wi가 현재 가방에 더 넣을 수 있는 무게 w보다 작은 경우이므로 넣을 수 있는 상태를 의미한다.
이 때, 왜 pi + P[i-1][w-wi]를 바로 넣지 않고, P[i-1][w]와 비교하는 것일까?
아이템을 추가하는 것이 무조건 더 큰거 아닌가?
아니다. 그 이유는 아래의 극단적인 예시를 살펴보자.
n=3, W=3
아이템1: 무게 1, 가치 100
아이템2: 무게 2, 가치 2
아이템3: 무게 3, 가치 4i \ w 0 1 2 3 0 P[0][0] = 0 P[0][1] = 0 P[0][2] = 0 P[0][3] = 0 1 (p=100, w=1) P[1][0] = 0 P[1][1] = 100 P[1][2] = 100 P[1][3] = 100 2 (p=2, w=2) P[2][0] = 0 P[2][1] = 100 P[2][2] = 100 or 2 P[2][3] = 102 3 (p=4, w=3) P[3][0] = 0 P[3][1] = 100 P[3][2] = 100 P[3][3] = 102 or 3 P[2][2]의 자리에는 무게 2의 아이템을 집어넣을 수 있다.
따라서 P[2][2] = max(P[1][2], 2 + P[1][0])의 식을 얻을 수 있다.
여기서 P[1][2] = 100, 2 + P[1][0] = 2 이다. 즉, 2를 추가했는데도 오히려 추가 안 한 경우보다 낮은 값이 나온다.
여기서 위 식의 의미를 파악, 해석해볼 수 있다.
아이템의 무게가 부분 가방의 무게 한계치보다 무겁다면 아이템을 추가하지 않지만,
가볍다면, 아이템을 추가하게 되는데, 그 과정에서 아이템의 교체가 이루어지는 경우 (위의 경우에는 아이템1을 빼고 2를 넣는 경우)
교체된 가방의 이득이 교체하기 전보다 이득이 적다면? 아이템을 넣지 않는게 더 이득이 큰 것이라고 해석할 수 있다.
시간 복잡도는 다음과 같다.
- i=n: 1 entry
- i=n-1: 2 entries
- ...
- i=1: 2^(n-1) entries
즉 1 + 2 + 4 + ... + 2^n = Θ(2^n)의 시간 복잡도를 갖는다.
Backtracking
백 트래킹 방식으로 해결하는 접근 방식은 다음과 같다.
(참고로 다시 리뷰하자면 Backtracking 방식은 depth-first search 방식을 사용한다.
이후에 나올 branch and bound 방식에서는 breadth-first, best-first 방식도 등장한다)
우선 Node에서 관리하는 값과는 별개로 글로벌로 maxProfit값을 관리한다.
탐색이 종료되는 시점의 maxProfit의 값이 최적해가 될 것이고,
탐색하는 과정에서 maxProfit보다 값이 커지는 경우 이 값을 업데이트 하는 방식으로 진행된다.
탐색의 효율성을 위해서 역시 promising 개념을 도입한다.
- NonPromising Node
upper bound를 설정하여 최대 이득의 상한선을 설정한다. (아래 노드를 아무리 탐색해도 이보다 비싸질 수는 없다는 조건)
이 상한선은 아무렇게나 정해도 된다. (사실 큰 상수 하나 집어넣어도 된다)
하지만, 탐색 시간을 줄이기 위해 실제로 도출될 상한값과 가까울 수록 좋은데, 연산시간도 고려해야 한다.
이 경우에는 fractional knapsack의 최대 이득을 upper bound로 설정한다.
가망이 없는 노드는 아래의 세 가지 경우 중에 하나이다.
- 가방에 넣은 아이템의 무게가 최대 가방이 담을 수 있는 무게(W)보다 무거운 경우
- 가방에 넣지 않은 모든 아이템을 넣어도 maxProfit에 도달하지 못하는 경우
- upper bound보다 maxProfit이 큰 경우
- Promising Node
NonPromising Node가 아닌 노드.
이제 의사코드로 구현해볼건데, 그 전에 몇가지 규칙을 정하자.
W: 가방이 최대로 담을 수 있는 무게
maxProfit: 현재까지의 최대 이득을 저장
numBest: 현재 어느 depth(item i)까지 고려한 상태인지 저장
이 값으로 include의 유효한 index를 파악할 수 있다.
유효한 index를 파악해야 하는 이유는 백 트래킹 하는 과정에서 include에 있던 값을 비워주는 작업을 하지 않기 때문
bestSet: 최대 이득이 되는 item 집합
include[i]: item i 포함 여부public static void knapsackBT(index depth, int profit, int weight) { // 가방 최대 무게에 도달하지 않았으며, maxProfit보다 이득이 큰 경우 // maxProfit과 그 아이템의 여부 갱신. if (weight <= W && profit > maxProfit) { maxProfit = profit; numBest = depth; bestSet = include; } if (!promising(depth, profit, weight)) return; include[i+1] = true; knapsackBT(depth+1, profit+p[i+1], weight+w[i+1]); include[i+1] = false; knapsackBT(depth+1, profit, weight); } public static boolean promising(index depth, int profit, int weight) { index searchDepth; int totWeight; float upperBound; // 1조건 위배: 가방에 넣은 아이템의 무게가 최대 가방이 담을 수 있는 무게(W)보다 무거운 경우 if (weight >= W) return false; searchDepth = depth+1; totWeight = weight; upperBound = profit; // 전체 탐색을 하며 && overweight가 되지 않을 때 까지 // upperBound 갱신. while (searchDepth <= n && totWeight + w[searchDepth] <= W) { totWeight += w[searchDepth]; upperBound += p[searchDepth]; searchDepth++; } // 위 반복운을 overweight 컨디션 때문에 빠져나간 경우, // partition 무게까지 더해줌. if (searchDepth <= n) { upperBound += p[searchDepth] * (W-totWeight) / w[searchDepth]; } // 2조건 위배: 가방에 넣지 않은 모든 아이템을 넣어도 maxProfit에 도달하지 못하는 경우 // 3조건 위배: upper bound보다 maxProfit이 큰 경우 return upperBound > maxProfit; }각 스탭에서 아이템을 포함할건지 안 할건지 2가지 경우의 수가 존재하기 때문에
시간 복잡도는 1 + 2 + 4 + ... + 2^n = Θ(2^n)를 갖는다.
Branch and Bound (Breadth-first search)
분기 한정 방식에서 Breadth-first search 방법으로 탐색하여 해결하는 접근 방식은 다음과 같다.
promising개념을 도입하여 트리의 탐색범위를 줄이고 bestSol값을 업데이트 하는 방식이다.
사실 백 트래킹과 같은 원리로 진행된다.
Promising Node만 탐색하고, upper bound 설정하고...
다만, 탐색 순서가 Breadth-first 이기 때문에, 노드를 탐색하고 바로 양쪽 자식 노드를 재귀호출하는 방식이 아닌,
Queue에 enqueue하고, 다음 루프에서 dequeue된 노드를 탐색하는 방식으로 진행된다.
좋은 그림 설명으로 대체한다.
(글로 분석하며 적는건 TSP - Branch and Bound에서 해서 지침...)
이를 의사코드로 구현하면 다음과 같다.
public class node { int level; int profit; int weight; } // n: # of item // p: items' profits // w: items' weights // W: knapsack max weight public static void knapsackBreadth(int n, int[] p, int[] w, int W) { queue Q; node u, v; int bestSol; initialize(Q); v.level = 0; v.profit = 0; v.weight = 0; bestSol = 0; enqueue(Q, v); while (!Empty(Q)) { dequeue(Q, v); u.level = v.level + 1; // left child - item 추가 u.weight = v.weight + w[u.level]; u.profit = v.profit + p[u.level]; if (u.weight <= W && u.profit > bestSol) { bestSol = u.profit; } if (bound(u) > bestSol) { enqueue(Q, u); } // right child - item 추가 안 함 u.weight = v.weight; u.profit = v.profit; if (bound(u) > bestSol) { enqueue(Q, u); } } return bestSol; } public static float bound(node u) { int curLevel; int totWeight; float result; // 가방 무게를 초과한 경우 upper bound를 0으로 하여 탐색 안하도록 함. if (u.weight >= W) return 0; result = u.profit; curLevel = u.level + 1; totWeight = u.weight; // 전체 탐색을 하며 && overweight가 되지 않을 때 까지 // result(upper bound) 갱신. while (curLevel <= n && totWeight + w[curLevel] <= W) { totWeight += w[curLevel]; result += p[curLevel]; curLevel++; } // 위 반복운을 overweight 컨디션 때문에 빠져나간 경우, // partition 무게까지 더해줌. if (curLevel <= n) { result += p[curLevel] * (W-totWeight) / w[curLevel]; } return result; }Branch and Bound (Best-first search)
이 역시 Breadth-first와 거의 동일하다.
차이점이라곤 Queue 대신 Priority Queue를 사용한다는 점 뿐이다.
바로 의사코드로 구현해보자.
public class node { int level; int profit; int weight; float bound; // priority queue를 위해 미리 계산하고 값을 저장. } // n: # of item // p: items' profits // w: items' weights // W: knapsack max weight public static void knapsackBest(int n, int[] p, int[] w, int W) { priorityQueue PQ; node u, v; int bestSol; initialize(PQ); v.level = 0; v.profit = 0; v.weight = 0; v.bound = bound(v); bestSol = 0; enqueue(PQ, v); while (!Empty(PQ)) { dequeue(PQ, v); // upper bound가 bestSol보다 작으면 탐색하지 않음. if (v.bound <= bestSol) continue; u.level = v.level + 1; // left child - item 추가 u.weight = v.weight + w[u.level]; u.profit = v.profit + p[u.level]; u.bound = bound(u); if (u.weight <= W && u.profit > bestSol) { bestSol = u.profit; } if (u.bound > bestSol) { enqueue(PQ, u); } // right child - item 추가 안 함 u.weight = v.weight; u.profit = v.profit; u.bound = bound(u); if (u.bound > bestSol) { enqueue(Q, u); } } return bestSol; } public static float bound(node u) { int curLevel; int totWeight; float result; // 가방 무게를 초과한 경우 upper bound를 0으로 하여 탐색 안하도록 함. if (u.weight >= W) return 0; result = u.profit; curLevel = u.level + 1; totWeight = u.weight; // 전체 탐색을 하며 && overweight가 되지 않을 때 까지 // result(upper bound) 갱신. while (curLevel <= n && totWeight + w[curLevel] <= W) { totWeight += w[curLevel]; result += p[curLevel]; curLevel++; } // 위 반복운을 overweight 컨디션 때문에 빠져나간 경우, // partition 무게까지 더해줌. if (curLevel <= n) { result += p[curLevel] * (W-totWeight) / w[curLevel]; } return result; }'대학 > 알고리즘' 카테고리의 다른 글
Theory of NP (0) 2023.06.11 Computational Complexity Analysis - Sorting problem (2) 2023.06.11 Traveling SalesPerson Problem (Branch and Bound) (2) 2023.06.10 Sum of subsets Problem (0) 2023.06.10 N Queens Problem (0) 2023.06.10