백준 12865 평범한 배낭 [JavaScript / Node.js]

문제

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

 

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다.

4 7 // N K
6 13 // W V
4 8 // W V
3 6 // W V
5 12 // W V

접근

배낭 문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭 문제를 분할 가능 배낭 문제(Fractional) -Greedy 문제 , 짐을 쪼갤 수 없는 경우의 배낭 문제를 0-1 배낭 문제(0-1 Knapsack) - DP문제 라 부른다. - 위키백과

 

해당 문제는 0-1 배낭 문제(0-1 Knapsack)로 DP로 접근한다.

DP문제는 문제의 답을 구하는 규칙성(점화식)을 빨리 찾는게 관건이다.(개인생각, 2023.02.022)

결론부터 말하면 문제의 점화식은 아래와 같다: 

DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]);

 

풀이

const fs = require("fs");

// 문제 링크 : https://www.acmicpc.net/problem/12865
// 제출 시 path : /dev/stdin

const input = fs
  .readFileSync("./input.txt")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => parseInt(v)));

const solution = (input) => {
  const [N, K] = input.shift();
  const weight = input.flat().filter((val, idx) => idx % 2 === 0);
  const value = input.flat().filter((val, idx) => idx % 2 !== 0);
  const dp = Array.from(Array(N + 1), () => Array(K + 1).fill(0));

  // 점화식: dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])

  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= K; i++) {
      if (j - weight[i] >= 0)
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
      dp[i][j] = dp[i - 1][j];
    }
  }

  return dp[N][K];
};
console.log(solution(input));

 

해설

왜 DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]); 인가?

인덱스 문제 때문에 arr[0] 부분을 형식상 채워준다.

 

row: 아이템1, 2, 3, 4

col: 현재 배낭의 무게

 

 

 

 

 

문제풀이는 이해가 가는데 계속 런타임 에러가 나는 이유를 모르겠다. 내일은 아래 보면서 이부분 디버깅 해봐야겠음.

let fs = require("fs");
let knapsack = fs.readFileSync("예제.txt").toString().split("\n");
const N = Number(knapsack[0].split(" ")[0]);
const K = Number(knapsack[0].split(" ")[1]);
knapsack = knapsack.map((element) =>
  element
    .trim()
    .split(" ")
    .map((value) => Number(value))
);
const weight = [];
const value = [];
for (let n = 0; n <= N; n++) {
  weight.push(knapsack[n][0]);
  value.push(knapsack[n][1]);
}

const dp = Array.from(new Array(N + 1), () => new Array(K + 1));

for (let i = 0; i <= N; i++) {
  dp[i][0] = 0;
}
for (let j = 0; j <= K; j++) {
  dp[0][j] = 0;
}
for (let j = 1; j <= K; j++) {
  if (knapsack[1][0] <= j) {
    dp[1][j] = knapsack[1][1];
  } else {
    dp[1][j] = 0;
  }
}

for (let i = 2; i <= N; i++) {
  for (let j = 1; j <= K; j++) {
    if (j < weight[i]) {
      dp[i][j] = dp[i - 1][j];
    } else {
      // 현재 물건을 포함하지 않는 경우 : dp[i - 1][j]
      // 현재 물건을 포함하는 경우: dp[i-1][j - weight[i]] + value[i]
      dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
  }
}
console.log(dp[N][K]);