백준 - 12865 평범한 배낭 (DP) JS

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

 

 

문제는 최대로 담을 수 있는 무게와 담으려는 물품이 주어질 때, 배낭에 넣을 수 있는 물건들의 가치합의 최대값 요하는 문제다.

// limit = 5
// data = [ [ '6', '13' ], [ '4', '8' ], [ '3', '6' ], [ '5', '12' ] ]

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split("\n").map((x)=> x.split(" "))

const [_, limit] = input.shift().map(el=> +el)

console.log(input)
function solution(data) {
  let table = Array.from({length : limit + 1}, ()=> 0)

  data.forEach((el)=> {
    const [w,v] = el.map(el=> +el)
    for(let i = limit ; i > w - 1 ; i--) 
      table[i] = Math.max(table[i], table[i-w] + v)
  })

  console.log(table.at(-1))
}
solution(input)

 

로직은 다음과 같이 구현했다.

먼저 각 무게별로 가치를 담을 수 있게 table이라는 배열을 무게 + 1의 길이만큼 생성한 뒤 기본값으로 0을 넣어주었다.

이후 반복문을 순회하며, 이전 값을 참조한 값으로 다이나믹 프로그래밍으로 table를 재할당한다.

 

// data = [ [ '6', '13' ], [ '4', '8' ], [ '3', '6' ], [ '5', '12' ] ]

  data.forEach((el)=> {
    const [w,v] = el.map(el=> +el)
    for(let i = limit ; i > w - 1 ; i--) 
      table[i] = Math.max(table[i], table[i-w] + v)
  })

반복문을 통해 산출되는 table은 위와 같이 나타낼 수 있다.

조금 설명을 하자면,

1회차에서는 table[6~7]에 가치 13을 할당하고, table[0~5] 에는 무게가 6인 물품을 담지 못하기 때문에 스킵한다. (table의 기본값을 0으로 두고 for문을 역순으로 설계한 이유기도하다.)

 

여기서부터 중요한데,  2회차부터는 현재 물품을 담을 때의 가치와, 담지 않을 때의 가치를 비교하며 table에 할당한다.

table[4]와, table[6]을 비교하면,

table[4]의 경우 기존 table[4]가 0이었기 때문에, 무게가 "4"일 때부터 담을 수 있는 물품의 가치인 "8"이 할당되었고,

table[6]의 경우, 기존 table[6]이 13로, 담으려는 물품의 가치 table[4](이때 해당 값은 0) + 8 보다 크기 때문에 "13"이 유지가 된다.

 

3회차의 table[7]의 경우, 기존 table[7](13) 인 값이, table[4](8) + 새로 들어오는 물품(6)의 값보다 작기 때문에 "14"가 할당된다.

(기존 배낭이 [6,13]으로 채워져 있다고 한다면, 3회차 순회로 인해 배낭이 [4,8],[3,6]으로 채워져있음을 의미한다.)

 

이런 순으로 순회를 마친 뒤, 가장 큰 가치일 table의 마지막 값을 리턴하면 로직이 마무리된다.