[바미] Dynamic programming - 0/1 Knapsack Problem 알고리즘 구현하기.

Knapsack problem?

Knapsack problem은 동적 계획법을 이용하여 효율적으로 해결할 수 있는데요. 이를 위해서는 다이나믹 프로그래밍의 개념을 이해해야 합니다.

다이나믹 프로그래밍(Dynamic Programming)은 복잡한 문제를 간단한 하위 문제로 나누어 해결하는 알고리즘인데

중복되는 하위 문제들을 한 번만 계산하여, 전체 문제를 해결하는 효율적인 방법을 제공합니다.

Knapsack problem의 경우, 각 아이템을 배낭에 넣거나 넣지 않을 수 있으므로, 하위 문제는 아이템을 넣을지 말지에

따라 달라지죠. 따라서, 각 아이템마다 넣을지 말지에 대한 선택지를 가지고, 모든 가능한 선택지에 대해서 최대 가치를

계산해야 해요. 이 때, 각 선택지에 대한 최대 가치는 이전 선택지에 대한 최대 가치를 이용하여 계산할 수 있기 때문에

이 문제는 다이나믹 프로그래밍 기법을 이용하여 해결할 수 있습니다.

구현

function knapsack(capacity, weights, values, n) {
  const dp = [];

  // 0부터 capacity까지의 모든 무게에 대해서 최대 가치를 계산합니다.
  for (let i = 0; i <= n; i++) {
    dp[i] = [];
    for (let j = 0; j <= capacity; j++) {
      if (i === 0 || j === 0) {
        // 첫 번째 행과 첫 번째 열의 값을 0으로 초기화합니다.
        dp[i][j] = 0;
      } else if (weights[i - 1] <= j) {
        // 현재 아이템을 배낭에 넣을 수 있는 경우
        dp[i][j] = Math.max(
          values[i - 1] + dp[i - 1][j - weights[i - 1]], // 현재 아이템을 넣는 경우
          dp[i - 1][j] // 현재 아이템을 넣지 않는 경우
        );
      } else {
        // 현재 아이템을 배낭에 넣을 수 없는 경우
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

  // 마지막 행, 마지막 열에 저장된 최대 가치를 반환합니다.
  return dp[n][capacity];
}

코드 설명

위에서 소개한 배낭 문제는 다이나믹 프로그래밍의 Bottom-up 방식으로 해결하였습니다.

dp 배열을 2차원 배열로 선언합니다. 이 때, 각 행은 아이템의 개수에 해당하고, 각 열은 배낭의 무게에 해당합니다.

dp[i][j]는 i번째 아이템까지 고려하고, 배낭의 무게가 j일 때의 최대 가치를 의미합니다.

먼저, dp 배열의 첫 번째 행과 첫 번째 열을 0으로 초기화합니다. 그리고 1부터 n까지의 모든 아이템에 대해서, 0부터 capacity까지의 모든 무게에 대해 최대 가치를 계산합니다.

 

아이템을 넣을 수 있는 경우, 현재 아이템을 넣는 경우와 넣지 않는 경우 중에서 더 큰 가치를 선택합니다. 이때, 현재 아이템을 넣는 경우의 최대 가치는 현재 아이템의 가치와, 현재 아이템의 무게를 제외한 배낭의 무게에서 이전 아이템까지의 최대 가치를 더한 값입니다.

아이템을 넣을 수 없는 경우, 현재 아이템을 배낭에 넣을 수 없으므로 이전 아이템까지의 최대 가치를 그대로 저장합니다.

 

예를 들어보죠.

const values = [60, 100, 120];
const weights = [10, 20, 30];
const capacity = 50;
const n = values.length;

console.log(knapsack(capacity, weights, values, n)); // 220

결과는 220이 나와야 합니다. 즉, 가치가 60인 물건과 가치가 100인 물건을 배낭에 넣고 총 무게가 30이 됩니다. 

이 후에 가치가 120인 물건을 넣을 수 없으므로, 이전에 넣은 물건을 그대로 두고 최대 가치를 얻게 됩니다.

 

언제 쓰이는지?

0/1 Knapsack Problem 알고리즘은 물품 배낭 문제를 해결하기 위한 대표적인 알고리즘 중 하나입니다. 이 알고리즘은 배낭에 담을 수 있는 물품의 가치와 무게를 고려하여 최대 가치를 얻을 수 있는 물품의 조합을 찾는 문제에 적용됩니다.

실제로 배낭 문제는 다양한 분야에서 활용되며, 예를 들어 생산 공정에서 재료를 최대한 효율적으로 사용하기 위한 생산 계획에 적용될 수 있습니다. 또한, 컴퓨터 네트워크에서도 데이터 전송을 최대한 효율적으로 처리하기 위한 라우팅 알고리즘 등에 활용될 수 있습니다. 배낭 문제는 이러한 분야에서 최적화 문제를 해결하는 데에 필요한 기초적인 도구 중 하나이며, 0/1 Knapsack Problem 알고리즘은 배낭 문제를 해결하기 위한 가장 기본적인 알고리즘 중 하나입니다.