알고리즘/알고리즘

알고리즘 - 배낭 문제 (Knapsack Problem)

배낭 문제 (Knapsack Problem)

알고리즘 문제 중에 다음과 같은 문제들이 나올 때가 있습니다.

어떤 가방에 담을 수 있는 무게가 한정되어있을 경우,
가방에 담을 수 있는 아이템들의 가치의 최대 합은?

최대로 담을 수 있는 무게가 주어진 배낭과 무게와 가치를 지닌 물건들이 각각 한 개씩 주어졌을 때, 배낭에 담을 수 있는 최대 가치의 합을 찾는 문제를 배낭 문제라고 합니다.

이런 문제는 다음과 같은 유형으로 나눠집니다.

분할 가능한 배낭 문제 (Fractional Knapsack Problem)

분할 가능한 배낭 문제는 주어진 아이템들을 분할해서 배낭에 담을 수 있는 문제들을 뜻합니다.

분할이 가능하다면, 무게당 가치를 계산해서 배낭에 넣으면 되는데, 이는 그리디 알고리즘으로 풀 수 있습니다.

그리디로 풀기

위의 이미지를 토대로 그리디로 풀어보도록 하겠습니다.

아이템별 무게당 가치를 계산해보면 다음과 같습니다.

A : 약 0.3/kg
B : 2/kg
C : 2.5/kg
D : 1/kg
E : 1/kg

가치가 높은 아이템에 우선순위를 부여하여 최대로 배낭에 담는다면 다음과 같이 계산됩니다.

최대 무게 = C 4kg + B 1kg + D 1kg + E 2kg + A 7kg = 15kg
최대 가치 = 4*2.5 + 2*1 + 1*1 + 1*2 + 0.3*7 = 약 16.1

0 - 1 배낭 문제 (0 - 1 Knapsack Problem)

0-1 배낭문제의 경우, 분할 가능한 배낭 문제와 달리 그리디 알고리즘으로 풀 수 없습니다.

브루트 포스나 동적 계획법, 백트래킹을 이용하여 풀 수 있습니다.

여기서는 브루트 포스, 동적 계획법 두가지 방법에 대해 설명하도록 하겠습니다.

브루트 포스로 풀기

가방에 담을 수 있는 모든 경우의 수를 돌아보는 방법입니다.

가방에 담을 수 있는 모든 경우의 수는 해당 아이템이 들어가거나, 안 들어가거나 두 가지로 나눠지므로 시간 복잡도가 다음과 같이 계산됩니다.

A	B	C	D	E
들어감	들어감	들어감	들어감	들어감
안들어감	안들어감	안들어감	안들어감	안들어감

시간 복잡도 = O(2^N)

알고리즘에서 2^N의 시간이 걸린다는 것은 N이 작다면 풀어볼만 하겠지만, 조금만 크더라도 엄청난 시간이 걸리게 되므로 되도록이면 Knapsack문제에선 브루트 포스로 풀지 않는 것이 좋습니다.

동적 계획법으로 풀기

브루트 포스에서는 전부 탐색을 하느라 오래걸렸지만, 최대한 이 문제를 쪼개서 푼다면 적은 시간으로도 풀 수 있습니다.

먼저, 앞서 이야기한 것 처럼 물건이 포함되거나 미포함되는 경우를 생각해 봅시다.

한 아이템으로 특정 무게에서 얼마만큼의 가치를 낼 수 있는지 다음과 같이 표(dp)로 나타낼 수 있습니다.

여기서 A로 가방을 채우는 경우, 무게별로 다음과 같은 가치를 가질 수 있습니다.

B가 들어가는 경우는 다음과 같습니다.

B의 무게는 1kg이기 때문에, 배낭이 1kg인 경우부터 채워넣을 수 있습니다.

그런데 만약 배낭의 무게가 12kg인 경우, 문제가 발생합니다.

현재 12kg의 최대 가치는 A가 들어가있는 4입니다. 여기서 B를 넣게 되면 B의 무게가 추가되어 13kg이 되기 때문에 넣을 수가 없습니다. 그렇다면 주어진 선택지는 다음과 같습니다.

B가 들어갈 공간을 확보하고 넣는 경우
B를 안넣는 경우

위의 경우 나올 수 있는 가치를 식으로 나타내보면 다음과 같습니다.

B가 들어갈 공간을 확보하고 넣는 경우 = (현재 배낭 무게 - B의 무게)의 최대 가치 + B의 가치
B를 안넣는 경우 = 현재 배낭 무게의 최대 가치

두 경우에서 나올 수 있는 값 중 큰 값을 해당 배낭의 최대 가치로 생각할 수 있습니다. 이를 정리하여 식으로 표현하면 다음과 같습니다.

현재 배낭 무게 : W
현재 배낭의 최대 가치 : W_v
아이템의 무게 : I_w
아이템의 가치 : I_v
W_v = Max( (W - I_w)_v + I_v , W_v )

위의 식을 이용하여 전개해보면 다음과 같이 나옵니다.

B 공간을 확보하고 넣는 경우 = (12-1)의 가치인 0 + B의 가치 2 = 2
B를 넣지 않는 경우 = A가 들어가 있는 4
Max(4 , 2) = 4

최종적으로 4가 들어가게 됩니다.

위와 같은 과정을 거쳐 배낭 무게가 13일 때를 계산해보면 다음과 같습니다.

이 과정을 아이템 E까지 반복하게 되면 다음과 같은 표가 완성됩니다.

동적 계획법을 이용하면 시간복잡도는 O(무게 * N)이 나오게 됩니다.

프로그래밍 언어로 구현하기

Java

0 - 1 배낭 문제

브루트 포스

// 재귀로 브루트 포스 구현
public static int bruteForce(int[] weight, int[] value, int idx,
   int kSum, int vSum, int K) {

   // 재귀 탈출, 끝까지 탐색했다면, 무게를 체크해보고 넘으면 필요가 없으니 0, 안넘으면 가치 합 리턴
   if (idx == weight.length) {
      if (kSum <= K) {
         return vSum;
      }
      return 0;
   }

   // 해당 아이템 포함
   int contain = bruteForce(weight, value, idx + 1, kSum + weight[idx], vSum + value[idx], K);
   
   // 해당 아이템 미포함
   int except = bruteForce(weight, value, idx + 1, kSum, vSum, K);

   // 포함한 가치와 미포함한 가치의 최대치 비교
   return Math.max(contain, except);
}

동적 계획법

public static int dp(int[] weight, int[] value, int K) {

   // 첫번째 행을 비어있는 행으로 만들어 계산을 편하게 하기 위해 행의 개수 + 1 해줍니다.
   int[][] dp = new int[weight.length + 1][K + 1];

   // 아이템 순회
   for (int i = 0; i <= weight.length; i++) {
      // 무게 순회
      for (int w = 0; w <= K; w++) {
         if (i == 0 || w == 0) {
            continue;
         } else if (weight[i - 1] <= w) { // i - 1을 해주는 이유는 현재 dp가 weight의 길이보다 1 많기 때문에 맞춰주기 위함
            dp[i][w] = Math.max(dp[i - 1][w - weight[i - 1]] + value[i - 1], dp[i - 1][w]);
         } else {
            dp[i][w] = dp[i - 1][w];
         }
      }
   }

   return dp[weight.length][K];
}

참고자료

https://www.youtube.com/watch?v=A8nOpWRXQrs

https://namu.wiki/w/%EB%B0%B0%EB%82%AD%20%EB%AC%B8%EC%A0%9C

'알고리즘 > 알고리즘' 카테고리의 다른 글

알고리즘 - 정렬 (0)	2023.05.18
알고리즘 - Union-Find (0)	2023.05.10
알고리즘 - 최소 비용 신장 트리 (MST) (0)	2023.05.10
알고리즘 - 최장 증가 부분 수열 (LIS) (0)	2023.04.28
알고리즘 - 알고리즘 복잡도 (0)	2023.04.11

Contents

새소식