평범한 배낭 [백준 알고리즘 12865]

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

12865번: 평범한 배낭

 

const input = ['4 7', '6 13', '4 8', '3 6', '5 12']
const [a, ...b] = input;
const [cases, weight] = a.split(' ').map(elem => Number(elem))
const weightValue = b.map(elem => elem.split(' ').map(elem => Number(elem)))

const counts = [];
for (let i = 0; i < cases+1; i++) {
  counts.push(new Array(weight+1).fill(0))
}

for (let i = 1; i < cases+1; i++) {
  const b_weight = weightValue[i-1][0];
  const b_value = weightValue[i-1][1];
  for (let j = 1; j < weight+1; j++) {
    if (j < b_weight) {
      counts[i][j] = counts[i-1][j]
    } else {
      const prev = counts[i-1][j];
      const update = counts[i-1][j-b_weight] + b_value
      counts[i][j] = Math.max(prev, update)
    }
  }
}
console.log(counts[cases][weight])