46_0-1Knapsack

이론은

https://cocoon1787.tistory.com/206 이거 보시면 편하실거에요!

이론이 너무 어렵습니다 ㅠㅠㅠ

 

const knapsack = function (weight, items) {
  let d =  Array.from(Array(items.length+1), () => Array(weight+1).fill(0))
  items.unshift([0,0]); //[[0,0], [10,60], [20,100], [30,120]] 이런식으로 오게하기 위해 넣은것
  
  for(let i=1; i<items.length; i++) {
    for(let j=1; j<=weight; j++) {
      if(j-items[i][0] >= 0) d[i][j] = Math.max(d[i-1][j], d[i-1][j-items[i][0]]+items[i][1]);
      else d[i][j] = d[i-1][j];
    }
  }
  return d[items.length-1][weight];
}