Knapsack(배낭알고리즘)

let ting = [{
  v:0,
  w:0,
}];

 

  for(let i=1; i<=n; i++) { // n개의 물건. (세로)
    for(let j=1; j<=k; j++) { // k무게 까지. (가로) 
      if(ting[i].w <= j) {  // 가방에 물건을 넣을 수 있다.
        // (i번째 물건을 위해서 (i-1)번쨰 물건을 뺀다, i번째 물건을 넣지 않는다.)
        dp[i][j] = Math.max(ting[i].v + dp[i-1][j-ting[i].w], dp[i-1][j]);
      } 
      else if(ting[i].w > j) {  // 가방에 물건을 넣을 수 없다.
        dp[i][j] = dp[i-1][j];
      }
    }
  }

1. i 번째 물건이 배낭에 넣을 수 있는 무게인지 확인.

2. i 번째 물건을 넣기위해서 다른 물건을 빼고 넣을것인가? 아니면 i번째 물건을 넣지 않을 것인가.