[백준] 12865 평범한 배낭

문제 설명

N개의 물건에 대한 무게 W와 가치 V가 주어졌을 때 배낭에 넣을 수 있는 최대 무게 K가 주어질 때 배낭에 들어갈 수 있는 물건의 가치 최댓값을 구하는 문제다.

문제 풀이

이 문제는 DP 냅색 알고리즘을 사용하는 대표적인 문제다. DFS로 시도를 해봤지만 시간초과가 발생했다.

먼저 dp 테이블을 만든다. dp 테이블의 행은 주어진 1~N까지의 물건이다. 그리고 열은 1~K까지 가방에 물건을 넣은 무게를 의미한다. 행과 열이 만나는 각각의 칸은 N번까지의 물건을 확인해봤을 때 K무게의 가방이 가질 수 있는 최대 가치를 갖는다.

이 문제를 작은 문제들로 나누면 물건을 넣었을 때와 넣지 않았을 때로 구분할 수 있다. 물건을 넣었을 때에는 물건이 들어갈 수 있는지 확인해준다. 물건을 넣을 수 있는 경우에는 기존의 최댓값과 물건을 하나 빼고 새로운 물건을 넣었을 때의 가치를 비교하는 식으로 dp 테이블을 작성한다.

제출 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [nk, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, K] = nk.split(" ").map(Number);
const arr = input.map((v) => v.split(" ").map(Number));
const dp = Array.from({ length: N + 1 }, () => Array(K + 1).fill(0));
for (let i = 1; i <= N; i++) {
  for (let j = 1; j <= K; j++) {
    if (j >= arr[i - 1][0]) {
      dp[i][j] = Math.max(dp[i - 1][j - arr[i - 1][0]] + arr[i - 1][1], dp[i - 1][j]);
    } else {
      dp[i][j] = dp[i - 1][j];
    }
  }
}
console.log(dp[N][K]);

출처:
평범한 배낭 https://www.acmicpc.net/problem/12865