백준 GOLD 5(평범한 배낭)

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2023-02-02

  • 해결 방법 :

    • dp를 활용해 문제 해결
    • (N + 1, K + 1) 크기의 dp 배열 생성
    • 각 물건 별로 K까지의 모든 dp를 업데이트
      • 현재 물건의 무게가 k보다 큰 경우 이전 물건 dp의 값
      • 작은 경우 이전 물건 dp의 값과 현재 물건의 가치(V) + 이전 물건 dp에서 W만큼 뺀 dp의 값(dp[i][k - W]) 중 큰 값
        • 즉, 현재 물건을 넣을 수 있는 k라면 현재 물건을 넣었을 때의 가치와 이전 물건 dp의 가치 중 큰 값

  • 회고 :

    • x

  • 코드

    const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
const input = fs.readFileSync(filePath).toString().trim();

solution(input);

function solution(props) {
  props = props.split('\n');
  const [N, K] = props[0].split(' ').map((e) => +e);
  const dp = Array.from({ length: N + 1 }, () => Array(K + 1).fill(0));

  props.slice(1).forEach((prop, i) => {
    const [W, V] = prop.split(' ').map((e) => +e);

    for (let k = 1; k <= K; k++) {
      dp[i + 1][k] = W > k ? dp[i][k] : Math.max(V + dp[i][k - W], dp[i][k]);
    }
  });

  console.log(dp[N][K]);
}

  • 출처: 백준