배낭 문제 (Knapsack Problem)

배낭에 담을 수 있는 무게의 최대값이 정해져 있고,

가치와 무게가 정해져 있는 짐을 배낭에 담을 때,

가치의 합이 최대가 되도록하는 짐의 조합을 찾는 문제

 

1. 물건을 쪼갤 수 없어서 무게와 가치가 무조건 정수형태를 가지는 유형

다이나믹 프로그래밍(DP, Dynamic Programming)을 사용해야 한다.

 

EX ) 최대 무게는 7이고, 각 물건의 무게와 가치는 다음과 같다.

          =>  [6, 13], [4, 8], [3, 6], [5, 12]

 

1) 가로는 가방의 최대 무게 / 세로는 가방에 들어간 물건의 개수이다.

j   /   i	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1
2
3
4

 

2) [6, 13] 물건을 집어 넣는다.

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2
3
4

   - 최대 무게가 현재 무게보다 작은 경우 ( DP[1][2] )

       => 바로 위의 값을 가져온다 ( DP[0][2] )

   - 최대 무게가 현재 무게보다 크거나 같은 경우 ( DP[1][7] )

       => 바로 위의 값 ( DP[0][7] ) /  현재 가치 ( 13 ) + [ 최대 무게 - 현재 무게 ] 위치의 가치 ( DP[0][1] ) 를 비교한다.

 

❗점화식 ❗

   현재 집어 넣는 물건의 가치 : v

   현재 집어 넣는 물건의 무게 : w

 

   ( w > j ) DP[i][j] = DP[i-1][j]

   (w <= j ) DP[i][j] = Math.max(DP[i-1][j], v + DP[i-1][j-w])

 

3) [4, 8] 물건을 집어 넣는다.

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3
4

 

4) [3, 6] 물건을 집어 넣는다.

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
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

 

5) [5, 12] 물건을 집어 넣는다.

	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
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

 

자바스크립트 코드

const fs = require('fs');
const filePath = process.platform==='linux' ? '/dev/stdin':'input.txt';
const input = fs.readFileSync(filePath).toString().split('\n');

const [n, k] = input[0].split(' ').map(Number);
const objects = input.slice(1).map((v) => v.split(' ').map(Number));

let dp = Array.from(Array(n+1), () => Array(k+1).fill(0));

for (let i = 1; i <= n; i++) {
  const [w, v] = objects[i-1];
  
  for (let j = 1; j <= k; j++) {
    if (w > j) {
      dp[i][j] = dp[i-1][j];
    } else {
      dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w] + v);
    }
  }
}

console.log(dp[n][k]);