들어가며

메모이제이션, 동적 프로그래밍의 기초같은 문제다. 처음 이 문제를 접하고 당황했다.
무엇을 위해서, 어떤 해결 방안을 위해서 이런 동작이 생겼나 짚어보았다. 그 다음 코드를 한 줄씩 다시 써보면서 주석을 달았다.

문제

배낭 채우기 문제 (knapsack problem)는 유명한 조합 최적화 문제로 아래와 같이 정의됩니다.

• 한쪽에 배낭 하나와 이 배낭에 담을 수 있는 무게의 최댓값이 정해져 있습니다. 다른 한쪽에는 일정한 가치와 무게를 가진 짐들이 있습니다. 이때 배낭에 담을 수 있는 여러 짐들의 조합들 중 가치의 합이 최대가 되는 조합을 찾아야 합니다.

배낭의 무게(weight)와 물건에 대한 정보들을 요소로 갖는 배열(items)을 받아 배낭에 담을 수 있는 최대 가치를 리턴해야 합니다.

핵심 개념

2차원 배열을 쓰는 방법도 있지만 난 cached 배열을 활용하는게 더 마음에 든다. 메모리를 아끼고 직관적으로 문제를 바라볼 수 있다.

• 아이템을 기준으로 반복문을 실행한다.
• 아이템별로 가장 최적의 수를 찾는다. (possible 배열)
• 이전 최적값 cached 배열 에서 무게(wt)를 차감하면서 생기는 가치(v)를 비교한다.
• 더 효율적이라면 possible 배열을 갱신한다.
• 새로운 possible 배열은 이제 cached 배열이다.

Javascript Code

const knapsack = function (weight, items) {
  // cached 배열은 항상 최선의 값을 저장함. 최종 반환할 값을 가지고 있음
  let cached = Array(weight + 1).fill(0);
  // 가방보다 무게가 큰 아이템 제외
  items = items.filter((item) => item[0] <= weight);
  // 아이템별로 반복문을 실행. [wt, v] 로 구조분해 할당
  items.forEach(([wt, v]) => {
    // 임시 값이 들어갈 possible 배열. cached에서 값을 받아오고 새로운 아이템을 대입해서 비교
    const possible = Array(weight + 1).fill(0);
    for (let i = 1; i <= weight; i++) {
      possible[i] = cached[i];
      // 새로운 값과 현재 최선의 값을 비교.
      if (i - wt >= 0 && cached[i - wt] + v > cached[i]) {
        possible[i] = cached[i - wt] + v; 
      }
      // 더 작은 무게가 더 효율적인 경우 해당 값으로 변경
      if (cached[i - 1] > cached[i]) {
        possible[i] = cached[i - 1];
      }
    }
    // 최적화 판단이 끝난 배열을 cached 배열에 저장
    cached = possible;
  })
  return cached[weight]
};