🎒 Knapsack 알고리즘 (배낭 알고리즘)

🎒 배낭 알고리즘

DP 알고리즘 중 하나

주어진 공간(배낭)에 최대 가치를 가지는 물건들을 넣도록 물건들을 선택하는 것이다.

 

배낭 알고리즘에는 2가지 유형이 존재한다.

 

1️⃣ Fraction Knapsack

• 물건을 쪼갤 수 있는 경우
• 이 경우는 그리디 알고리즘이 사용될 수 있다.
  • 단위 무게당 가치가 높은 물건을 차례대로 배낭에 넣는 방식

 

2️⃣ 0-1 Knapsack

• 물건을 배낭에 넣을지 (1) 또는 넣지 않을지(0)을 결정하는 경우

 

🤔 왜 배낭 알고리즘이 Dynamic Programming 일까?

 

결국 최대 이익을 구하기 위해서는 물건을 배낭에 넣어야 한다.

• 이때, 배낭에 물건을 넣는냐 마느냐 가 중요한 선택이다.
  • 2가지 선택지가 존재

 

만약, 배낭에 넣을 수 있는 양이 N 이고, 넣고자 하는 물건의 무게가 M 이라 할 때, 선택할 수 있는 경우의 수는 2가지이다.

 

1️⃣ 물건을 배낭에 넣는 경우 - 가방의 공간이 (N - M) 남는다.

 

2️⃣ 배낭에 넣지 않는 경우 - 가방의 공간이 그대로 N 으로 남는다.

 

↪️ 다른 접근 방식

최대 N 만큼의 양을 담을 수 있는 배낭에 무게가 M, 가치가 K인 물건을 담는다면?

- 현재 가치가 K가 되며 배낭에 최대 N-M 만큼을 더 넣을 수 있게 된다.

 

ex) 10 kg을 담을수 있는 배낭의 최대 가치

= (3kg 물건의 가치) + 최대 7kg을 담을 수 있는 배낭의 최대 가치

= (3kg 물건의 가치) + (1kg 물건의 가치) + 최대 6kg을 담을 수 있는 배낭의 최대 가치

 

이렇게 부분의 답을 이용해서 큰 부분의 답을 만들고 해당 부분들의 답이 전체의 답이 되는 DP의 특징이 보이게 된다.

 

🤖 변하는 2가지

해당 알고리즘을 구현하는데 있어서 변하는 값은 2가지 이다.

• 배낭의 최대 무게
• 담을 수 있는 물건의 개수 및 종류

 

따라서 2차원 배열을 사용해서 각 경우의 수에 따른 답을 저장해주어야 한다.

 

최대이익[i][w] = K

• 최대 무게가 w 인 가방에서 i 번째 물건까지 판단했을 때의 최대 가치
• ex) 최대이익[4][6] : 최대 무게 6kg인 배낭에서 4번째 물건까지 진행했을 때의 최대 가치

 

🧑🏻‍💻 i 번째 다음 물건인 i + 1 번째 물건을 탐색할 때의 최대 가치를 구해보자

• 2가지 경우의 수가 존재

 

1️⃣ 해당 물건의 무게가 최대 배낭 무게(W)를 초과하는 경우

• 이 경우는 물건을 배낭에 넣을 수 없어 최대 가치의 값은 이전 최대 가치 값(K)으로 유지된다.
• dp[i + 1][w] = dp[i][w]

 

2️⃣ 물건의 무게(M)가 최대 배낭 무게(W)를 초과하지 않는 경우

• 이 경우는 선택에 따라 또 2가지 경우의 수로 분리된다.
• 2 - 1. 해당 물건을 배낭에 넣는 경우 :  dp[i + 1][w] = dp[i][w - m] + (i + 1 물건의 가치)
• 2 - 2. 해당 물건을 배낭에 넣지 않는 경우 : dp[i + 1][w] = dp[i][w]
• 따라서 dp[i][w] = max(dp[i - 1][w], i 가치 + dp[i - 1][w - m])

 

🧑🏻‍💻 코드

int[][] dp = new int[K + 1][W + 1]; // K번까지의 물건, 배낭의 무게 W

for(int i = 1; i <= K; i++) {
  for(int j = 1; j <= W; j++) {
    if(j - product[i].weight >= 0) {
     // 해당 물건을 넣을 수 있는 경우 
       dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - product[i].weight] + product[i].value);
    }
    else {
      dp[i][j] = dp[i - 1][j];
    }
  }
}

 

📕 참고자료

배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기