baekjoon. 평범한 배낭

문제

---

풀이

---

표를 이용해서 설명하는게 가장 빠르겠다

j는 가방의 무게로 오른쪽으로 갈 수록 넣을 수 있는 무게가 1씩 늘어난다

i는 i번째 물건까지를 넣는 상황을 고려한다는 뜻하며 0은 아무것도 넣지 않은 상태, 1은 무게 6, 가치 13의 물건 한가지만 넣는다고 가정

2가된다면 1번, 2번 물건만 넣는 상황을 가정한다

i\j	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13

위의 표를 보면 첫번째 물건은 무게 6에 가치 13이기때문에 가방의 무게가 6과 7일때만 들어감을 알 수 있다

여기서 6과 7일때 첫번째 물건을 넣고 난 후 가방의 남은 무게가 0과 1인데

0과 1에 넣을 수 있는 물건(dp[1][0],dㅔ[1][1])은 현재로써는 없기 때문에 고려하지않는다

i\j	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13

두번째 물건까지는 가방의 크기가 4일 때 부터 들어갈 수 있다

4와 5는 8이지만 6부터는 첫번째 물건을 넣는 것이 가치가 더 크기때문에 (8과 13을 비교) 13을 넣는다

여기서도 마찬가지로 4부터 7까지 물건을 넣고 난 후 남은 크기에 넣을 물건은 없기때문에 고려하지 않고

i\j	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14

여기서가 문제, 3일때 6을 넣고 평소대로 늘려가다가 7일때 세번째 물건을 넣고 나면 남는 자리에 (dp[3][4] : 8) 가치 8의 물건이 들어가있다

6+8이 13보다 크기 때문에 가방 무게가 7일때의 가장 큰 값은 14로 대체된다

여기서 얻을 수 있는 식은 dp[i][j] = Math.max(dp[i][j-i] + i번째 무게의 가치, dp[i-1][j])이다

코드

  const input =`4 7
6 13
4 8
3 6
5 12`.split('\n').map(v=>v.split(' ').map(v=>Number(v)));
  const input = require("fs").readFileSync("/dev/stdin").toString().trim().split('\n').map(v=>v.split(' ').map(v=>Number(v)));


  const cache = Array(input.length+1).fill(0).map(()=>Array(K+1).fill(0).map(()=>0));

  for(let i=0;i<input.length;i++){
      for(let j=1;j<=K;j++){
          const W = input[i][0];
          const V= input[i][1];
          if(W<=j) cache[i+1][j] = Math.max(V+cache[i][j-W],cache[i][j]);
          else cache[i+1][j]= Math.max(cache[i+1][j-1],cache[i][j]);
      }
  }

  console.log(cache[input.length][K]);

와 같다