백준 12865 < 평범한 배낭 > JavaScript

📍문제 링크

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

📍알고리즘 분류

- 다이나믹 프로그래밍
- 배낭 문제
 

📍문제 풀이

배낭 문제(Knapsack Problem) 로 알려진 유명한 문제
- 메모이제이션을 이용하지 않으면 시간이 매우 매우 오래걸린다
- DP를 이용하면 O(N * K) 로 해결 가능
 
데이터 수 N과, 최대 배낭의 무게 K가 주어진다.
N개의 줄에 아이템의 무게 W, 가치 V 가 주어질 때, 무게 기준을 만족시키면서 가치의 최대값을 구하라
(변수들은 모두 정수)
 
각 아이템의 무게를 순회하며 가능한 최대 무게를 채워나가는 방향으로 해결한다
- 1, 2, ... N 번 아이템을 순회하면서, 지금까지의 최댓값을 계속 이용한다 (memoization)
- 현재 아이템을 배낭에 넣고도 여유가 있는 순간부터, 무게가 허용하는 직전의 최댓값을 이용할 수 있는지 살핀다
 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [N, K] = input[0].split(" ").map(Number);
  const data = input.slice(1).map((row) => row.split(" ").map(Number));
  const memo = Array.from({ length: N + 1 }, (_) =>
    Array.from({ length: K + 1 }, (_) => 0),
  );

  for (let i = 1; i <= N; i++) {
    const [W, V] = data[i - 1];
    for (let j = 1; j <= K; j++) {
      // j : 가능한 최대 무게
      if (j - W >= 0) {
        // j - W : 여유분 (가능한 최대 무게 - 현재 아이템 무게)
        // 새 아이템의 무게를 넣는 경우와 안 넣는 경우 중 더 큰 가치를 따짐
        memo[i][j] = Math.max(memo[i - 1][j], memo[i - 1][j - W] + V);
      } else {
        memo[i][j] = memo[i - 1][j];
      }
    }
  }
  console.log(memo[N][K]);
});