백준 JS 12865번 평범한 배낭. Knapsack

1. 첫 번째 시도

처음 문제를 봤을 때 들었던 생각은 재귀를 이용한 완전탐색.

const fs = require('fs');
const Data = fs.readFileSync('/dev/stdin').trim()
  .split("\\n").map(v => v.split(" ").map(Number));

const [N,K] = Data.shift()
Data.sort((a,b)=>b[1] - a[1])
let answer = 0;

function additem(bag,index,w,v) {
  if(index === N){
    if(answer < v){
      answer = v
    }
    return
  }
  const newbag = [...bag]
  additem([...newbag],index+1,w,v)

  const [W,V] = Data[index]
  if(W+w <= K){
    newbag.push(V)
    additem([...newbag],index+1,w+W,v+V)
  }
}
additem([],0,0,0)
console.log(answer)

백준에선 런타임 에러(TypeError)라고 떴다. 그건 둘째치고 애초에 이 문제를 풀 때 재귀를 이용하게 된다면 2^100이라는 시간복잡도를 가지게 되는 만큼 절때 풀 수 없다.

---

2. 두 번째 시도

이 문제는 1차원 배열로 DP를 만들기에는 변수가 무게, 가치 두가지로 주어져 불가능 했다.

그래서 2차원 배열로 만들면 어떨까라는 생각으로 접근하였고, 2차원 배열로 만들면 쓸데없이 순회하는 구조가 될 것 같아서 Map 객체로 생성하여 아래와 같이 코드를 작성하였다.

const fs = require('fs');
const Data = fs.readFileSync('/dev/stdin').toString().trim().split("\\n").map(v => v.split(" ").map(Number))

const [N, K] = Data.shift()

const arr= Array.from({length:N},()=>new Map())
const [a, v] = Data[0]
arr[0].set(a,v)

let answer
if(a <= K){
  answer = v;
}else {
  answer = 0;
}

for(let i=1; i<N; i++){
  const [W, V] = Data[i]
  if(W <= K){
    arr[i].set(W,V)
    if(answer < V){
      answer = V
    }
  }
  for(let [key,value] of arr[i-1]){
    if(! arr[i].get(key) ||
      arr[i].get(key) < value){
      arr[i].set(key,value)
    }
    if(key+W <= K){
      if(!arr[i].get(key+W) || 
      arr[i].get(key+W) < value + V){
          arr[i].set(key+W,value+V)
          if(answer < value+V){
            answer = value+V
          }
      }
    }
  }
}
console.log(answer)

간단하게 설명한다면 물건들을 순회하는데, 순회 하는 물건의 이전 물건들을 통해서 만들 수 있는 {무게 : 최대가치}를 저장하는 방식.

4 7
6 13
4 8
3 6
5 12

위와 같은 input이 주어진다면,,

첫번째 순회의 객체는 {6:13}

두번째는 {6:13, 4:8, 10:21} 여기서 최대무게가 7이기 때문에 {4:8, 6:13}이 된다.

세번째는 {6:13, 4:8, 3:6 ,9:19, 7:14} 무게제한 ⇒ {6:13, 4:8, 3:6 , 7:14}

마지막 {6:13, 4:8, 3:6 , 7:14, 5:12 ,11:25, 9:20, 8:18, 12:26} 무게제한 ⇒ {6:13, 4:8, 3:6 , 7:14, 5:12}

해서 최대 가치값은 14가 된다.

---

다시 코드를 보니 첫번째 물건을 Map객체에 넣고, 순회를 i=1로 시작했는데 불필요한 코드인 것 같다. 그냥 i=0으로 시작하면 될 듯.