JavaScript로 해결하는 0/1 배낭 문제 (Knapsack Problem)

0/1 배낭 문제란?

"0/1 배낭 문제"는 주어진 아이템들 중 일부를 선택해 제한된 무게 안에서 가치를 최대로 만드는 조합을 찾는 대표적인 "동적 계획법" 문제입니다. 각 아이템은 한 번만 선택할 수 있으며, 쪼갤 수 없습니다. 이 문제는 물류 최적화, 자원 분배, 게임 인벤토리 설계 등 다양한 분야에 활용됩니다.

문제 조건 요약:

• 각 아이템은 무게(weight)와 가치(value)를 가짐
• 아이템은 쪼갤 수 없으며, 선택하거나 선택하지 않음
• 배낭에는 정해진 "무게 제한"이 있음
• 선택한 아이템들의 "총 무게"는 제한을 넘을 수 없음
• 가능한 조합 중, "가치의 합이 최대"가 되도록 선택

예: 무게가 [2, 3, 4, 5], 가치가 [3, 4, 5, 6]인 아이템과 capacity = 5가 주어졌을 때, 최대 가치는 7입니다 (무게 2, 3짜리 아이템 선택).

---

JavaScript로 구현하기 (Bottom-Up DP 방식)

function knapsack(weights, values, capacity) {
  const n = weights.length;
  // DP 배열 생성: (n+1) x (capacity+1)
  const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));

  // DP 배열 채우기
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if (weights[i - 1] <= w) {
        // 현재 아이템을 선택할 수 있는 경우
        const include = values[i - 1] + dp[i - 1][w - weights[i - 1]];
        const exclude = dp[i - 1][w];
        dp[i][w] = Math.max(include, exclude);
      } else {
        // 무게 초과로 선택 불가
        dp[i][w] = dp[i - 1][w];
      }
    }
  }

  // 최적 가치 반환
  return dp[n][capacity];
}

// 예제 실행
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 5;

console.log(knapsack(weights, values, capacity)); // 출력: 7 (3+4)

---

코드 설명

• dp[i][w]는 i번째 아이템까지 고려했을 때, 무게 w로 만들 수 있는 최대 가치를 의미합니다.
• 각 아이템마다, 현재 배낭 무게 w에 대해 다음 두 가지 선택지를 비교합니다:
  • 선택하지 않음: 이전 상태값 dp[i-1][w]
  • 선택함: values[i-1] + dp[i-1][w - weights[i-1]]
• 최종 결과는 dp[n][capacity]에 저장됩니다.

---

실행 결과 시각화 (DP 테이블 변화 과정)

아래 이미지는 알고리즘 실행 중 dp[i][w] 배열이 어떻게 변화하는지를 각 단계별로 보여줍니다. 인덱스 i는 아이템, w는 무게입니다.

압축파일에는 각 프레임이 이미지로 포함되어 있어, DP 테이블이 어떻게 채워지는지 하나하나 추적할 수 있습니다.

---

시간 및 공간 복잡도 분석

• 시간 복잡도: O(n * capacity)
• 공간 복잡도: O(n * capacity) (최적화 시 O(capacity)까지 줄일 수 있음)

이러한 방식은 배낭 문제를 효율적으로 해결할 수 있는 가장 일반적인 접근 중 하나입니다.

---

실전 활용 사례

• 물류 및 자원 배분 최적화
• 게임 인벤토리 설계 (무게 제한과 가치 고려)
• 마케팅 예산 배분 전략

---

마무리

0/1 배낭 문제는 동적 계획법을 익히는 데 매우 좋은 예제입니다. 코드의 흐름, DP 테이블의 작성 원리, 상태 전이 식의 의미를 명확히 이해하는 것이 중요합니다.

"최적화 문제"나 "DP 유형 분류" 등과도 연결되는 개념이므로, 다양한 변형 문제에도 도전해 보시길 추천드립니다.