[백준] 12865. 평범한 배낭 (자바스크립트/node.js/javascript/동적 계획법/동적 프로그래밍/다이나믹 프로그래밍)

 

문제를 풀기 위한 아이디어

동적 프로그래밍의 대표적인 유형 중 하나인 0/1 배낭 문제이다.

(배낭문제에 대한 포스트는 지난 게시글에 올렸으니 참고하실 분들은 참고하시면 됩니다.)

 

내가 작성한 코드 (자바스크립트)

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]);