[백준] 평범한 배낭 (javascript)

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

12865번: 평범한 배낭

 

 

🤔 해결방법

1. dp 배열을 생성하고 0으로 초기화
2. 각 물건에 대해 가능한 모든 무게(j)에 대해 dp[j] 값을 갱신 (새로운 dp[j]는 기존의 dp[j]와 dp[j - 물건 무게] + 물건 가치 중 큰 값으로 갱신)
3. dp 배열의 k번째 요소 출력

 

 

🔑 풀이

처음에는 물건의 무게가 최대 무게와 같은 경우와 작은 경우로 나눠 풀었다.

 

1. 물건의 무게가 최대 무게와 같은 경우
현재 최대 가치보다 크면, 최대가치 = 그 물건의 가치

 

2. 물건의 무게가 최대 무게보다 작은 경우
최대 무게와 같거나 작아질 때까지 다음 물건들의 가치를 합침
그 값이 현재 최대 가치보다 크면, 최대 가치 = 그 값

 

이를 바탕으로 다음과 같은 코드를 짰는데 예제의 정답은 출력했으나 백준에 제출하니 런타임 에러가 떴다.😥

const input = require("fs")
    // .readFileSync("/dev/stdin")
    .readFileSync(__dirname + "/input.txt")
    .toString()
    .trim()
    .split("\n");

  const [n, stuffsMax] = input[0].split(" ").map(Number);

  // 물건들 이중 배열로 담기
  let stuffs = [];
  for (let i = 1; i <= n; i++) {
    let [stuff, value] = input[i].split(" ").map(Number);
    stuffs.push([stuff, value]);
  }

  let currentMax = 0;
  for (let i = 0; i < stuffs.length; i++) {
    // 물건의 무게가 최대 무게와 같은 경우
    if (stuffs[i][0] === stuffsMax) {
      currentMax = Math.max(currentMax, value);
    }

    // 물건의 무게가 최대 무게보다 작은 경우
    else if (stuffs[i][0] < stuffsMax) {
      let stuffSum = stuffs[i][0];
      let valueSum = stuffs[i][1];

      for (let j = i + 1; j < stuffs.length; j++) {
        if (stuffSum <= stuffsMax) {
          stuffSum += stuffs[j][0];
          valueSum += stuffs[j][1];
          if (stuffSum > stuffsMax) continue;
          currentMax = Math.max(currentMax, valueSum);
        }
      }
    }
  }
  console.log(currentMax);

문제에서 주어진 무게의 최대값이 10만이기에 주어진 물건 수가 많아지고 각 무게 값도 더 커진다면 시간복잡도가 너무 높아지기 때문인 것 같았다.

따라서 다음과 같이 DP로 풀어야 하는 문제였다.

const input = require("fs")
    // .readFileSync("/dev/stdin")
    .readFileSync(__dirname + "/input.txt")
    .toString()
    .trim()
    .split("\n");

  const [n, k] = input[0].split(" ").map(Number);
  let dp = Array(k + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    const [w, v] = input[i].split(" ").map(Number);

    for (let j = k; j >= w; j--) {
      dp[j] = Math.max(dp[j], dp[j - w] + v);
    }
  }

  console.log(dp[k]);

dp 배열을 모두 0으로 초기화하고, 배열의 크기를 k + 1로 설정한다.

각 물건에 대한 정보를 순회하는데 물건을 배낭에 넣을 수 있는지 확인하고, 넣을 수 있다면 dp 테이블을 업데이트한다.

이 부분에서 물건을 넣을 수 있는 모든 가능성을 고려하기 위해 역순으로 순회하게 된다. 

dp[j]는 현재 최대 가치고 dp[j - w] + v는 새 물건을 추가했을 때의 가치이다.
둘 중 더 큰 값을 dp[j]에 저장하는 것이다.

마지막으로 dp[k]는 배낭의 무게가 k일 때의 최대 가치이므로 이 값을 출력하면 된다.

 

문제의 예제를 대입해보면 다음과 같은 과정으로 돌아간다.

아이템의 개수 n = 4
  가방의 최대 무게 k = 7

  물건 1: 무게 6, 가치 13
  물건 2: 무게 4, 가치 8
  물건 3: 무게 3, 가치 6
  물건 4: 무게 5, 가치 12
  초기 dp 배열: [0, 0, 0, 0, 0, 0, 0, 0] (k+1개의 0)

  물건 1 (무게 6, 가치 13)
  j = 7: dp[7] = max(dp[7], dp[7-6] + 13) = max(0, 0 + 13) = 13
  j = 6: dp[6] = max(dp[6], dp[6-6] + 13) = max(0, 0 + 13) = 13
  dp 배열: [0, 0, 0, 0, 0, 0, 13, 13]

  물건 2 (무게 4, 가치 8)
  j = 7: dp[7] = max(dp[7], dp[7-4] + 8) = max(13, 0 + 8) = 13
  j = 6: dp[6] = max(dp[6], dp[6-4] + 8) = max(13, 0 + 8) = 13
  j = 5: dp[5] = max(dp[5], dp[5-4] + 8) = max(0, 0 + 8) = 8
  j = 4: dp[4] = max(dp[4], dp[4-4] + 8) = max(0, 0 + 8) = 8
  dp 배열: [0, 0, 0, 0, 8, 8, 13, 13]

  물건 3 (무게 3, 가치 6)
  j = 7: dp[7] = max(dp[7], dp[7-3] + 6) = max(13, 8 + 6) = 14
  j = 6: dp[6] = max(dp[6], dp[6-3] + 6) = max(13, 0 + 6) = 13
  j = 5: dp[5] = max(dp[5], dp[5-3] + 6) = max(8, 0 + 6) = 8
  j = 4: dp[4] = max(dp[4], dp[4-3] + 6) = max(8, 0 + 6) = 8
  j = 3: dp[3] = max(dp[3], dp[3-3] + 6) = max(0, 0 + 6) = 6
  dp 배열: [0, 0, 0, 6, 8, 8, 13, 14]

  물건 4 (무게 5, 가치 12)
  j = 7: dp[7] = max(dp[7], dp[7-5] + 12) = max(14, 8 + 12) = 14
  j = 6: dp[6] = max(dp[6], dp[6-5] + 12) = max(13, 0 + 12) = 13
  j = 5: dp[5] = max(dp[5], dp[5-5] + 12) = max(8, 0 + 12) = 12
  dp 배열: [0, 0, 0, 6, 8, 12, 13, 14]

  결과: dp[7] = 14