[Nodejs] 12865번 평범한 배낭

문제 설명

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

12865번: 평범한 배낭

 

문제 풀이 방법

이 문제는 꽤나 유명한 DP문제 중 배낭문제이다.

처음 문제에 접근할 때 DFS으로 접근했지만 시간초과 에러가 발생해 DP 풀이를 참고했다.

 

물건의 총 갯수 n, 넣을 수 있는 총 무게 maxWeight를 이용해

각 물건을 넣는 시도를 할 때마다 각 무게에서의 최대 가치값을 측정하기 위해

가로가 maxWeight + 1, 세로가 n + 1인 2차원 배열을 생성해준다.

(+1을 한 이유는 이미 계산된 값을 이용하는 DP의 특징을 위해서이다. 처음 계산할 때 비교/가져올 값 설정)

 

그리고 점화식은

각 무게에서 가치의 최대값을 정해주는 식으로

((해당 무게 - 지금 넣을려는 물건의 무게)의 가치 + 지금 넣을려는 물건의 가치)와

이전 계산에서 가져온 해당 무게에서의 가치를 비교해 더 큰쪽을 넣어준다.

arr[i][j] = Math.max(arr[i - 1][j - W] + V, arr[i - 1][j])

 

 

코드

const path = __dirname + '/예제.txt'; // /dev/stdin
let input = require('fs').readFileSync(path).toString().trim().split('\n').map(e => e.split(' ').map(Number));

const [n, maxWeight] = input.shift();
const things = input;

let arr = Array.from({ length: n + 1 }, () => Array(maxWeight + 1).fill(0));

for (let i = 1; i <= n; i++){
  const [W, V] = things[i-1];
  for (let j = 1; j <= maxWeight; j++){
    if (j - W >= 0) {
      // arr[i - 1][j - W] + V 에서 arr[i - 1][j - W]은 표현할 무게(j)에서 지금 넣을 무게 W를 뺀 무게에서의 값을 구하는 것이다.
      arr[i][j] = Math.max(arr[i - 1][j - W] + V, arr[i - 1][j]);
    }
    else {
      arr[i][j] = arr[i - 1][j];
    }
  }
}

console.log(arr)

 

이 문제는 다시한번 풀어보는 시간을 갖아야 겠다.

다른 분이 작성한 코드를 보고 이해하는데 꽤나 오랜 시간이 걸렸다...

배낭문제라는 개념을 처음 접해서 어떻게 푸는지도 몰랐다....