백준 12865번 평범한 배낭 - node.js

#백준

#JavaScript

#DP

박효진 (@gywlsp)

2021년 03월 10일

이 글은 백준 12865번 평범한 배낭을 풀이한다. 코드는 javascript로 구현하였다.

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 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)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

예제 입력 1

4 7
6 13
4 8
3 6
5 12

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

예제 출력 1

14

제한

  • 시간: 2초
  • 메모리: 512MB

풀이

접근

최대 K만큼의 무게를 담을 수 있는 배낭에 물건을 넣을 때, 물건들의 가치 최대 합을 어떻게 구할 수 있을까? 무게 순서대로 물건을 담는 그리디 알고리즘을 이용해 답을 구할 수 있다고 생각할 수도 있지만, 그럴 수 없다. 다음 반례들에서 이를 확인할 수 있다.

  1. 10kg 무게를 버틸 수 있는 가방에 물건의 무게가 작은 순서대로 물건을 넣을 때 → 오답: 6, 정답 : 10

    • 1kg, 가치 1
    • 2kg, 가치 1
    • 3kg, 가치 2
    • 4kg, 가치 2
    • 5kg, 가치 10

  2. 10kg 무게를 버틸 수 있는 가방에 무게가 큰 순서대로 물건을 넣을 때 → 오답: 10, 정답: 14

    • 10kg, 가치 10
    • 2kg, 가치 5
    • 1kg, 가치 9

물건을 넣는 모든 경우의 수를 따져야 답을 구할 수 있다. 어떤 물건은 배낭에 넣을 수도 넣지 않을 수도 있기 때문에, 배낭에 N개의 물건 중 몇 개를 선택해 넣는 경우는 2^N가지이다. 그러나 N이 클 때 시간 내에 2^N가지 경우를 확인할 수 없다.

집합 A를 n번까지의 물건들 중에서 물건들을 최적으로 고른(무게 합이 K 이하이면서 가치 합이 최대인) 집합이라고 하자. 이 문제는 다음과 같은 최적 부분 구조가 성립하기 때문에 동적 계획법을 이용해 풀 수 있다.

  • 집합 A가 n번 물건을 포함하지 않는다면, A는 n-1번까지의 물건들 중에서 최적으로 고른 부분집합과 같다.
  • 집합 A가 n번 물건을 포함한다면, A는 n-1번까지의 물건들 중에서 최적으로 고른 부분집합에 n번 물건을 넣은 것과 같다. (다만 n번 물건의 무게를 넣어도 무게가 K 이하일 때에만 n번 물건을 넣을 수 있다.)

maxVSum[n][k]를 n번까지의 물건들 중 최적으로 고른 물건들(무게 합이 k 이하이면서 가치 합이 최대인)의 가치 합이라고 하면, 위의 내용을 참고해 다음과 같은 점화식을 쓸 수 있다.

  • n번 물건의 무게가 배낭의 무게 한도보다 무거워 넣을 수 없을 때: maxVSum[n][k] = maxVSum[n-1][k]
  • 그 외: maxVSum[n][k] = Max(maxVSum[n-1][k], maxVSum[n-1][k-weight] + value)

n=1, k=0부터 n=N, k=K까지 이 과정을 반복하면 maxVSum[N][k]를 구할 수 있고 이것이 답이다. 이 과정의 시간복잡도는 O(NK)이기 때문에 입력의 크기가 최대일 때에도 시간 내에 문제를 풀 수 있다.

구현

코드

const input = [];

const strToNumArr = (str) => str.split(' ').map(Number);

require('readline')
  .createInterface(process.stdin, process.stdout)
  .on('line', function (line) {
    input.push(line.trim());
  })
  .on('close', function () {
    const [N, K] = strToNumArr(input.shift());
    const items = input.map((str) => strToNumArr(str));
    //물건 번호 맞추기 위해 맨 앞에 null 넣음
    items.unshift(undefined);

    //maxVSum[n][k]: n번까지의 물건들 중 몇 개를 골라,
    //그 무게 합이 k 이하인 경우들 각각의 가치 합 중 최댓값
    const maxVSum = [];
    for (let i = 0; i <= N; i++) {
      maxVSum.push(Array(K + 1).fill(0));
    }

    for (let n = 1; n <= N; n++) {
      const [weight, value] = items[n];
      for (let k = 0; k <= K; k++) {
        //물건의 무게가 k보다 클 때
        if (k < weight) {
          maxVSum[n][k] = maxVSum[n - 1][k];
        } else {
          maxVSum[n][k] = Math.max(
            maxVSum[n - 1][k], //n번 물건 안 담는 경우
            maxVSum[n - 1][k - weight] + value //n번 물건 담는 경우
          );
        }
      }
    }

    console.log(maxVSum[N][K]);
  });

TABLE OF CONTENTS