집합 - Knapsack

Knapsack

배낭에 물건을 담을 때, 물건의 무게와 가치를 고려하여 가장 높은 가치를 가질 수 있는 경우의 수를 구하는 알고리즘

물건의 개수가 1개인 경우(0/1)과 물건의 개수가 제한되어 있는 경우(Bounded), 물건의 개수가 제한되어 있지 않은 경우(Unbounded)가 있다.

먼저 물건을 무게를 기준으로 정렬한다. 그 후에 배낭에 넣을 수 있는 무게에 따른 가장 높은 가치의 경우의 수를 행렬로 구하고, 그 행렬을 역추적하여 가장 높은 가치를 가질 때 배낭에 들어가는 물건의 조합을 계산할 수 있다.

밑의 코드는 물건의 개수가 1개인 경우다.

const Knapsack = (items, values, bagSize) => {
  const itemLength = items.length;
  const matrix = Array(itemLength + 1)
    .fill(0)
    .map(() => Array(bagSize + 1).fill(0));

  for (let i = 1; i < itemLength + 1; i++) {
    for (let j = 1; j < bagSize + 1; j++) {
      if (j < items[i - 1]) {
        matrix[i][j] = matrix[i - 1][j];
      } else {
        matrix[i][j] = Math.max(
          values[i - 1] + matrix[i - 1][j - items[i - 1]],
          matrix[i - 1][j]
        );
      }
    }
  }

  const answer = [];

  let x = bagSize;
  let y = itemLength;

  while (y > 1) {
    if (matrix[y][x] !== matrix[y - 1][x]) {
      answer.unshift(items[y - 1]);
      x -= items[y - 1];
    }
    y -= 1;
  }

  return answer;
};