평범한 배낭

평범한 배낭

문제 정의:

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다.
N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 V만큼 즐길 수 있다.
최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다.
최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const input = fs.readFileSync(filePath, 'utf-8').trim().split('\n');
// N: 물품의 수, K: 배낭의 최대 수용 무게
const [N, K] = input[0].split(' ').map(Number);
const items = input.slice(1).map((el) => el.split(' ').map(Number)); // [[W1,V1],[W2,V2],...[Wn,Vn]]

//물건 번호와 인덱스를 맞추기 위해 맨 앞에 null 또는 [0,0] 넣음 -> n번째 아이템 === n번째 인덱스
items.unshift([0, 0]); // [null, [W1,V1],[W2,V2],...[Wn,Vn]]

function solution() {
  // maxVSum[n][k]: n번까지의 물건 범위에서 물건 무게 합이 k(배낭의 무게)가 되는 경우, 해당 물건들의 가치 합의 최대값
  const maxVSum = Array.from({ length: N + 1 }, (_v) => new 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 {
        // 물건의 무게가 k보다 작거나 같을 때
        maxVSum[n][k] = Math.max(
          maxVSum[n - 1][k], // n번 물건 안 담는 경우
          maxVSum[n - 1][k - weight] + value // n번 물건 담는 경우
        );
      }
    }
  }

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

thinking

백트레킹으로 부분집합을 만들어 최대 값을 찾을려고 했으나 해당 문제가 dp로 분류되었기에 dp로 풀어보자했다.
그러나 dp를 어떻게 정의해야하는 지 모르겠어서 결국 검색을 통해 문제를 풀었다.

knapsack(배낭) 알고리즘으로 유명한 문제였다.
무게를 쪼갤 수 있는 경우와 그렇지 못한 경우에 따라 배낭 문제를 푸는 알고리즘이 달라진다.

• 무게를 쪼개는 경우 Fraction Knapsack Problem으로 불리며 Greedy로 풀면된다.
• 무게를 쪼갤수 없는 경우 0/1 Knapsack Problem으로 불리며 DP로 풀면된다.

여기서 Fraction과 0/1 의미를 이해하기 위해 물건의 무게를 가지고 설명하자면

• Fraction은 해당 물건의 무게를 더 작은 무게들로 분할하는 경우를 뜻하며
• 0/1는 해당 물건의 무게를 분할할 수 없어서 해당 물건을 사용 안 하는 경우(0)와 사용하는 경우(1) 2가지에 대한 표현이다.

위의 문제의 경우 물건의 무게를 쪼갤 수 없는 경우로 0/1배낭 문제에 속한다.
즉 해당 물건을 사용하냐 안하냐에 따른 결과 값이 달라진다는 의미인데 이 의미는 아래 내용을 읽어보면 이해가 될 것이다.

경우의 수

해당 문제예시를 가지고 설명을 하면 4개의 물건이 있고 각 물건을 배낭에 넣거나 넣지 않는 경우
즉 1개 물건 당 2개의 경우가 있으므로 2^4가지의 경우의 수가 있다.

// n개의 물건이 주어지면 2^n경우의 수가 존재한다.
[0/1, 0/1, 0/1, 0/1] // 각 자리마다 사용하는 경우(1)와 사용하지 않는 경우(0) 표현

2^4가지의 경우 중 배낭의 무게인 k를 만족시키면서 가치의 합이 최대인 경우를 찾으면 된다.

DP 정의

dp의 정의는 아래와 같다.

dp[n][k]
: n번째까지 물건들 중에서 k무게까지 최대한 채워넣을 때, 채워진 물건들의 여러 경우 중 물건들의 가치합의 최대값

물건의 번호와 배열의 인덱스를 맞춰주기 위해 0번째에 해당하는 데이터를 넣어준다.
이 부분은 코드 중 items.unshift([0, 0]);에 해당 된다.
0번째 데이터로 0번째 물건의 무게와 가치를 넣어줬다.

그렇기에 dp[3][5]는 0번째 물건부터 3번째 물건까지 중에서 무게 5만큼 최대한 채워넣을 때의 최대 가치값이 된다.
(이해가 안된다면 아래 dp테이블 표를 해당 문제를 설명을 적어놨으니 읽어보자)

결국 dp는 (n+1)*(k+1)크기의 2차원 배열이 된다.

설명을 하기 쉽게 물건의 무게와 가치를 추상적으로 표현하면 아래와 같이 되고 이를 기반으로 설명해보자

w[n]: n번째 물건의 무게
v[n]: n번째 물건의 가치
k: 배낭의 무게

w[n]과 k의 관계에 따른 점화식

w[n]과 k의 관계를 생각해보자

• w[n] > k : n번째 물건의 무게가 k보다 큰 경우 => 결국 배낭에 넣지 못하는 경우
  n번째 물건을 선택해도 배낭에 넣을 수 없어 n-1번째 물건까지 범위에서 k무게를 채울 때의 최대 가치값이 할당된다.
  if(w[n] > k) dp[n][k] = dp[n-1][k]

• w[n] < k : n번째 물건의 무게가 k보다 작은 경우
  이 경우 배낭에 넣는 경우와 넣지 않은 경우 2가지를 고려해야한다.

  • n번째 물건을 넣는 경우
    n번째 물건의 무게를 포함해 최종 무게가 k가 되야하기 때문에 (k = w[n] + restW)
    n번째 물건의 무게(w[n])와 나머지(k-w[n])무게를 고려해야한다.
    (k-n번째 물건의 무게)만큼의 무게를 채우는 경우는 n-1번째 물건까지 범위에서 (k-w[n])무게를 채울 때의 최대 가치값이 되므로 아래와 같이 정의된다.
    현재 n번째 물건의 가치 + n-1번째까지의 범위에서 k-w[n]의 무게를 채울때의 최대 가치

    restW = k - w[n] // k무게에서 현재 n번째 물건의 무게를 뺀 나머지 무게
    if(w[n] < k) dp[n][k] = v[n] + dp[n - 1][k - w[n]]

  • n번째 물건을 안 넣는 경우
    n-1번째 물건까지 범위에서 k무게를 채울 때의 최대 가치값이 된다.

    if(w[n] < k) dp[n][k] = dp[n - 1][k]

• w[n] === k : n번째 물건의 무게가 k와 같은 경우
  이 경우도 n번째 물건을 채워 넣는 경우와 그렇지 않은 경우 2가지를 생각해야한다.

  • n번째 물건을 넣는 경우
    w[n]과 k 무게가 같기에 n번째 물건만 넣을 수 있다.

    if(w[n] === k) dp[n][k] = v[n]

  • n번째 물건을 안 넣는 경우
    n-1번째 물건까지 범위에서 k무게를 채울 때의 최대 가치값이 된다.

    if(w[n] === k) dp[n][k] = dp[n - 1][k]

따라서 위의 경우를 종합하면 아래와 같이 점화식을 세울 수 있다.

if(w[n]>k) dp[n][k] = dp[n - 1][k]
if(w[n]<k) dp[n][k] = max(v[n] + dp[n - 1][k - w[n]], dp[n - 1][k])
if(w[n]===k) dp[n][k] = max(v[n], dp[n - 1][k])

여기서 w[n]<k 와 w[n]===k 일 때의 점화식이 비슷해보여서 더 줄일 수 없을까 생각을 해보자. (사실 줄일 수 있으니 적는거다)

n번째 물건을 넣고 k무게에서 w[n]만큼 뺀 나머지를 생각해보면 k-w[n]이 되는데 점화식에 따라 나머지 무게의 최대 가치값은 dp[n-1]k-w[n]]이 된다.

k-w[n]>0 인 경우 dp[n-1]k-w[n]] 다양한 값을 가질 수 있다.

하지만 같은 경우 즉 k-w[n] === 0 인 경우를 생각해보자.
dp[n-1]k-w[n]] 점화식에 k-w[n] === 0 를 대입하면 dp[n-1][0]이 된다.
dp[n-1][0]은 0 무게를 채우는 경우이고 물건을 넣을 수 없기에 0의 값을 가지게 된다.
따라서 이런 경우 테이블에서도 최대 가치값을 모두 0 으로 초기화했다.
(dp를 0부터 시작하도록 만들어 물건이 0번째도 있고 무게가0인 경우도 있다. 무게 또는 물건의 순번이 0인 경우 모두 최대 가치값을 0으로 할당함)

따라서 w[n] === k 인 경우
dp[n][k] = max(v[n], dp[n - 1][k])을 dp[n][k] = max(v[n] + dp[n-1][0], dp[n - 1][k])이라 쓸 수 있고 0의 값을 추상적으로 바꾸면
dp[n][k] = max(v[n] + dp[n-1][k-w[n]], dp[n - 1][k])이 된다.

즉 w[n]<k인 경우와 w[n]===k인 경우는 점화식이 같게 된다.

최종 점화식

최종적으로 점화식은 아래와 같이 세워진다.

if(w[n]>k) dp[n][k] = dp[n - 1][k]
if(w[n]<=k) dp[n][k] = max(v[n] + dp[n - 1][k - w[n]], dp[n - 1][k])

dp테이블 채우기

물건의 개수(n)와 배낭의 무게(k)를 이용해 DP(테이블)을 직접 하나씩 채워보자.

물건의 개수 N : 4
배낭의 수용 무게 K : 7

물건	무게	가치
물건1	6	13
물건2	4	8
물건3	3	6
물건4	5	12

• 1물건까지 경우 dp[1][k]

  물건	무게	가치
  물건1	6	13

  dp테이블

  물건 \ k	0	1	2	3	4	5	6	7
  물건1	0	0	0	0	0	0	13	13

  1물건 무게가 6이라 k가 5이하인 경우 넣지 못하는 상황이므로 0의 가치를 가지게 된다.
  6과 7의 무게에서 무게 6을 넣을 수 있으므로 13의 가치를 가진다.

• 2물건까지 경우 dp[2][k]

  물건	무게	가치
  물건1	6	13
  물건2	4	8

  dp테이블

  물건 \ k	0	1	2	3	4	5	6	7
  물건1	0	0	0	0	0	0	13	13
  물건2	0	0	0	0	8	8	13	13

  2물건 무게가 4이기에 k가 3이하인 경우 물건을 넣지 못해 0의 가치를 가지게 된다.
  k가 4부터 2물건의 가치인 8의 값을 가지게 되는데 무게가 6이상인 경우 1물건의 가치가 13으로 더 높기에 1물건의 가치값을 가진다.
  더 자세히 설명을 하자면 k가 6인 경우를 보면 수용 무게가 6이기에 1물건 또는 2물건 중 1개만 선택이 가능하다
  1물건을 선택하면 k=6인 경우 딱 맞아 떨어지고 k=7인 경우 무게 1이 남는데 1무게를 채울 수 있는 물건이 없으므로 1물건 1개인 경우가 최대가 된다.
  2물건을 선택하면 k=6인 경우 2물건 무게 4만큼이 빠진 무게 2가 남게 되고 2를 채울 수 있는 물건이 없다. 따라서 물건2의 가치값을 가진다.
  k=7인 경우도 7-4=3이 되고 무게 3의 물건이 2번째 까지의 물건 범위에 없기에 물건2의 가치값을 가진다.
  그러므로 1물건을 선택할 때 최대 값을 가지게 되므로 13이 된다.

• 3물건까지 경우 dp[3][k]

  물건	무게	가치
  물건1	6	13
  물건2	4	8
  물건3	3	6

  dp테이블

  물건 \ k	0	1	2	3	4	5	6	7
  물건1	0	0	0	0	0	0	13	13
  물건2	0	0	0	0	8	8	13	13
  물건3	0	0	0	6	8	8	13	14

  k<=2경우 물건의 무게가 만족하는 경우가 없으므로 가치값은 0,
  k=3인경우 물건3의 무게가 3이므로 가치값은 6이된다.
  k=4인 경우 물건 3의 무게 3을 넣고 나머지 무게 1를 채우는 경우와 무게가 4인 물건2를 채우는 경우 2가지가 있다.
  물건 3를 채워 무게 3을 사용하면 나머지 무게1를 채워야하는데 무게 1이 되는 물건이 없으므로 가치값은 물건3의 가치값인 6
  물건 2를 채우면 나머지 무게가 없으므로 물건2의 가치값인 8
  두 경우 중 최대 가치값인 8이 할당된다.
  k=5 인경우 물건2 무게4를 넣고 나머지 무게1를 넣는 경우와 물건3 무게3을 넣고 나머지 무게 2를 넣는 경우 2가지
  물건2를 선택하면 나머지 무게1인 물건이 없으므로 물건2의 가치값 8
  물건3을 선택하면 나머지 무게2인 물건이 없으므로 물건3의 가치값 6
  따라서 가치값이 높은 8이 된다.
  k=6인 경우 물건1을 넣는 경우, 물건2를 넣고 나머지 무게2를 넣는 경우, 3물건을 넣고 나머지 무게3을 넣는 경우 3가지
  물건1을 넣는 경우 나머지 무게가 없으므로 가치값은 13
  물건2을 넣고 나머지 무게2를 넣어야하지만 무게2를 가진 물건이 없으므로 물건2의 가치값인 8
  물건3을 넣고 나머지 무게3을 넣어야하니만 무게3인 물건을 이미 사용했으므로 물건3의 가치값인 6
  따라서 최대 가치값은 13
  k=7인 경우 물건1+나머지무게1 경우, 물건2+나머지 무게3 경우, 물건3+나머지무게4 경우 총 3가지
  물건1을 넣고 나머지 무게 1인 물건이 없으므로 가치값은 13
  물건2를 넣고 나머지 무게 3을 채울 수 있는 물건은 물건3이 있으므로 물건2의 가치 + 물건3의 가치 = 14
  물건3을 넣고 나머지 무게 4를 채울 수 있는 물건은 물건2가 있으므로 물건3의 가치 + 물건2의 가치 = 14

• 4물건까지 경우 dp[4][k]

  물건	무게	가치
  물건1	6	13
  물건2	4	8
  물건3	3	6
  물건4	5	12

  dp테이블

  물건 \ k	0	1	2	3	4	5	6	7
  물건1	0	0	0	0	0	0	13	13
  물건2	0	0	0	0	8	8	13	13
  물건3	0	0	0	6	8	8	13	14
  물건4	0	0	0	6	8	12	13	14

  기존과 같은 논리로 k<=4까지는 똑같다
  k>=5인 경우부터는 4물건의 무게가5이고 가치가 12이므로 물건4를 포함해 고려해야한다.
  k=5인 경우 물건 2,3,4 의 무게가 각각 4,3,5 이므로 최대 가치값은 물건4 무게5인 12가된다.
  k=6인 경우 물건1 무게6을 채우는 경우, 물건2 무게4와 나머지 무게2를 채우는 경우, 물건3 무게3과 나머지 무게3을 채우는 경우, 물건4를 채우고 나머지 무게1을 채우는 경우 총 4가지
  각 경우의 가치값은 13, 8, 6, 12 이므로 최대 가치값은 13이 된다.
  k=7인 경우 물건1+나머지무게1, 물건2+나머지무게3, 물건3+나머지무게4, 물건4+나머지무게2 총 4가지
  각 경우의 가치값은 13, 14, 14, 12 이므로 최대 가치값은 14가 된다.