BOJ : 12865 평범한 배낭 (JS)

소스코드

let fs = require('fs');
const { join } = require('path');
const filePath = process.platform === "linux" ? "/dev/stdin" : "예제.txt";
let input = fs.readFileSync(filePath).toString().split('\n');
const c = console.log

let inputs = input[0].split(" ").map(Number)

let n = inputs[0]
let weight = inputs[1]

let w = []
let v = []

let dp = []

for(let i = 0 ; i< n+1 ; i++){
    dp[i] = []
    for(let j = 0 ; j < weight +1 ; j++){
        dp[i][j] = 0
    }
}
for(let i = 1 ; i < n+1 ; i++){
    let numbers = (input[i].split(' ').map(Number))
    w.push(numbers[0])
    v.push(numbers[1])
}

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

        }
    
    }
}

c(dp[n][weight])

 

풀이

다이나믹 프로그래밍 기법 중 냅색 알고리즘을 이용한 간단한(?) 배낭 문제라고한다.

 

냅색 알고리즘은 배낭에 담을 수 있는 최대값이 정해져 있고 배낭안에 가치가 최대가 되도록 짐을 고르는 문제이다.

 

점화식을 만들기 위해서 우선 n과 k(소스코드에서는 weight 라고 표기했다.) 가 주어지는데 n을 몇번째 물건을 담을지, k는 무게를 얼만큼 담을지를 정하는 dp테이블을 작성해준다.

 

이중 포문을 돌려 차례대로 식에 넣어주는데 만약 무게가 초과 한다면 이전에 들었던 물건을 들어주면 된다.

 

아닌 경우 이전에 들었던 물건과 현재 들고있는 물건 + 남은 무게를 채워주는 물건을 들어주면 된다.

 

 

 

표를 작성해주는데, k(가로축) 일때 최대의 가치를 적어주었다.

 

문제

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

12865번: 평범한 배낭