백준 12865 평범한 배낭

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

한 달 뒤 입대하는 준서를 위해서..

준서가 여행에 필요하다고 생각하는 N개의 물건에 대해 가져갈 수 있는 조합의 총 가치를 구한 다음에 여기서 최고의 가치를 지니는 조합을 리턴하면 된다.

N개의 물건과 최대 K의 무게라는 조건이 붙는다.

내가 처음에 선택했던 방식은 완전탐색방식이었다.

let input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
 
const [N, K] = input[0].split(" ");
 
const stuffs = input.slice(1);
 
let result = [];
 
function takeStuff(left, val, allStuffs, result) {
  allStuffs.forEach((stuff, idx) => {
    const [w, v] = stuff.split(" ").map((t) => parseInt(t));
    if (left - w >= 0)
      takeStuff(
        left - w,
        val + v,
        allStuffs.filter((_, i) => i !== idx),
        result
      );
  });
  result.push(val);
  return;
}
 
takeStuff(K, 0, stuffs, result);
console.log(Math.max(...result));
 

해당 문제를 하위의 문제들로 나누어보면

하나의 물건을 선택 -> 총 무게에서 해당 무게를 뺀 무게에서 가능한 물건들을 모두 구하기

해당 조건을 계속해서 반복해가면서, 바닥조건이 보일 때까지 반복하여 가치를 구해야 한다. 이러한 조건을 만족하기 위해서는 기존 내가 선택한 물건들에 대해서 어떤 물건을 이미 선택했는지를 알아야 하고, 현재까지 누적된 가치 또한 알아야 하기 때문에 나는 재귀적인 방식을 통해서 가치를 누적하면서도 모든 경우의 수에 대해서 배열에 넣어 해당 배열의 최댓값을 구하면 된다고 생각했다.

하지만 이러한 완전탐색은 답은 맞지만 시간이 오래걸린다는 단점이 있다.

따라서 해당 문제를 다이나믹 프로그래밍으로 다시금 접근해야 한다.

let input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
 
const [N, K] = input[0].split(" ").map(Number);
const stuffs = input.slice(1).map((line) => line.split(" ").map(Number));
 
const dp = Array(K + 1).fill(0);
 
for (let i = 0; i < N; i++) {
  const [w, v] = stuffs[i];
 
  for (let j = K; j >= w; j--) {
    dp[j] = Math.max(dp[j], dp[j - w] + v);
  }
}
 
console.log(dp[K]);

해당 방식은 dp 테이블을 만들고 해당 테이블을 활용하는 방식이다.

최대 K의 무게를 지닐 수 있을 때 가질 수 있는 최대의 가치를 dp[n] 에 기록해놓는다. 이후 만들어진 dp 테이블에 대해서 모든 물건들에 대해서 반복을 돌게 되는데, 하지만 이러한 물건에 대해서 그대로 dp 테이블을 도는 것이 아닌, 거꾸로 dp 테이블의 끝에서부터 해당하는 물건의 무게까지 dp 테이블을 돈다. 거꾸로 dp 테이블을 도는 이유는, 0부터 dp 테이블을 돌게 된다면 애초에 dp테이블의 w 이전 값들에 대한 값들은 전부 0이 될 수밖에 없다. n의 무게에서 최대로 가질 수 있는 가치를 기록해놓는 테이블이기 때문에 n 이전의 무게는 w가 더 무겁기 때문에 가치가 갱신될 것이 없다.

테이블을 도는 과정에서 dp[n]에 있는 수는 Math.max를 통해 최댓값을 기존 dp에 있는 값과의 비교를 통해 가치가 현재가 더 크다면 업데이트를, 더 크지 않다면 기존 값을 선택해서 dp테이블의 값을 갱신시킨다.