[JS][백준]12865_평범한 배낭

문제 번호

 

12865번: 평범한 배낭

 

 

 

알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

 

문제 풀이

 DP에서 유명한 배낭문제다. 처음풀었을땐 설명을 봐도 이해하기가 너무 어려웠다. 

DP문제이니만큼 이전에 계산했던 값들을 계속 사용하면서 문제를 풀 수 있다.

 DP라는 2차원 배열을 이용할건데 이때 2차원 배열의 내용은 value, 즉 '가치'가 된다. 세로축은 물건의 갯수, 가로축은 무게로 생각한다.

물건들 | 배낭 한계	0	1	2	3	4
무게0, 가치0	배낭한계가 0일때 배낭의 최고가치	배낭한계가 1일때 배낭의 최고가치	배낭한계가 2일때 배낭의 최고가치	배낭한계가 3일때 배낭의 최고가치	배낭한계가 4일때 배낭의 최고가치
무게 4, 가치7	배낭한계가 0일때 배낭의 최고가치	배낭한계가 1일때 배낭의 최고가치	배낭한계가 2일때 배낭의 최고가치	배낭한계가 3일때 배낭의 최고가치	배낭한계가 4일때 배낭의 최고가치
무게 6, 가치13	배낭한계가 0일때 배낭의 최고가치	배낭한계가 1일때 배낭의 최고가치	배낭한계가 2일때 배낭의 최고가치	배낭한계가 3일때 배낭의 최고가치	배낭한계가 4일때 배낭의 최고가치
무게 3, 가치6	배낭한계가 0일때 배낭의 최고가치	배낭한계가 1일때 배낭의 최고가치	배낭한계가 2일때 배낭의 최고가치	배낭한계가 3일때 배낭의 최고가치	배낭한계가 4일때 배낭의 최고가치

 이렇게 생겼다고 이해하면된다.

 

우선 배낭의 무게한계가 0이고, 물건의 갯수도 0일때를 생각해본다. 이때는 배낭속의 물건들의 가치의 총합이 0이다.

물건들 | 배낭 한계	0	1	2	3	4
무게0, 가치0	0	0	0	0	0
무게 4, 가치7	0
무게 6, 가치13	0
무게 3, 가치6	0

 

 이제 무게가 4이고 가치가7인 첫번째 물건을 넣을 수 있는지 확인해보자. 무게가 4인 물건을 넣으려면 배낭의 한계가 4이상이여야한다.

물건들 | 배낭 한계	0	1	2	3	4
무게0, 가치0	0	0	0	0	0
무게 4, 가치7	0	0	0	0	7
무게 6, 가치13	0
무게 3, 가치6	0

 

 배낭에 물건을 넣을 수 있을때 2가지 선택지가있다. 배낭에 i번째 물건을 넣을것인가? 넣지 않을것인가?

왜냐하면 이전의 물건들을 빼지않고 i번째 물건만 추가한다면 상관없지만, i번째 물건을 추가 하기위해서는 i번째 물건의 무게만큼 배낭에 여유가 있어야 하기 때문이다. 그렇기 때문에 i번째 물건의 무게만큼의 여유를 배낭에 만들어주기 위해서 이전의 물건을 빼는것이 더 높은 가치를 지니는지, i번째 물건을 포기하는것이 더 높은 가치를 지니는지를 판단해야한다.

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]);
      }

 dp[i-1][j-ting[i].w] +  ting[i].v는 i번째 물건(ting[i])를 넣기위해서 배낭에 공간을 만들고(dp[i-1][j-ting[i].w]) i번째 물건의 가치(ting[i].v)를 넣어본다. 

 dp[i-1][j]는 i번째 물건을 포기하고 (i-1)번째 물건까지만 넣는다.

이렇게 2개의 값을 비교하여 더 큰값을 dp[i][j]에 넣어주면 된다.

( 다른 블로그에도 좋은 설명들이 많다. 그래도 직접 손으로 써보면서 몇번 해보는게 젤 이해 잘됐던거같다.)

 

 만약 가방의 한계보다 물건의 무게가 더 무겁다면 가방에 물건을 넣을 수 없다.

이때도 i번째 물건을 포기하고 (i-1)번째 물건까지만 생각해본다.

 else if(ting[i].w > j) {  // 가방에 물건을 넣을 수 없다.
        dp[i][j] = dp[i-1][j];
      }

 

 

전체코드

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');

let [n,k] = input[0].split(' ').map(Number);
let ting = [{
  v:0,
  w:0,
}];
let dp = new Array(n+1).fill(null).map(_=>new Array(k+1).fill(0));

function sol(){
  
  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];
      }
    }
  }
  console.log(dp[n][k]);
}

function main(){
  for(let i=0; i<n; i++) {
    let [w,v] = input[i+1].split(' ').map(Number);
    ting.push({
      w:w,
      v,v,
    })
  }
  //console.log(ting);
  sol();
}
main();

 DP 배열을 (1,1) 부터 사용할것이기때문에 ting 배열에도 (v:0, w:0)을 추가해주어서 for문을 1부터 사용할 수 있도록 해줬다.

특이사항

 이해하는것도 어렵지만 설명하는건 몇배로 어렵다.