[JS] 백준 12865 : 평범한 배낭 - DP문제

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

12865번: 평범한 배낭

 

📋풀이방법

1. 첫번째 물건(무게 : 6, 가치 : 13)을 dp배열에 넣어서 검사한다.

2. 두번째 물건(무게 : 4, 가치:  8)을 넣어 검사해본다.

3. 세번째 물거(무게 : 3, 가치 : 6)

4. 이를 반복해준다.

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let [N,K]=input.shift().split(" ").map(Number);
let arr=[];
for (let i = 0; i < N; i++) {
    arr.push(input[i].split(' ').map(Number));
    
}
const dp = Array(K + 1).fill(0);

for (let i = 0; i < N; i++) {
    const [W, V] = arr[i];
    console.log(dp)
    for (let j = K; j >= W; j--) {
        if (dp[j - W] + V > dp[j]) {
            dp[j] = dp[j - W] + V;
        }
    }
}

console.log(dp[K]);

 

💢어려웠던 점

1. DP문제임을 파악하지 못했다

 -처음에 그리디 문제인줄 알고 정렬을 해서 풀었다.

2. DP배열에 값을 넣을 때 뒤에서 부터 넣어줘야 했다.

 -앞에서 부터하게 되면 만약 무게 : 2, 가치 :4 의 물건이 들어가는 상황이라면 

 -> dp[2]에서부터 4가 들어가다가 dp[4]에서는 dp[2]에서 4를 더한 8 이 들어가게된다.

 ->즉 물건의 중복이 생긴다.

 -> 그러므로 최대무게 7kg인 dp[7]에서 부터

 -> 들어오는 물건의 무게를 뺀 dp[7-weight] 의 값에서 가치를 더한 값과 비교해야한다.