[백준 12865] 평범한 배낭
February 21, 2023
문제
https://www.acmicpc.net/problem/12865
아이디어
각각의 물품에 대해서 배낭의 용량을 증가시키면서 특정 용량일 때 얼마만큼의 가치가 들어가는지를 계산하여 저장하고, 그 저장된 결과를 다음 물품을 계산할 때 참고하여 사용하면 된다.
-
각 물품의 특정 배낭 용량에 대해서 얼마만큼의 가치가 들어가는지를 기록하는 2차원 배열 dp를 선언한다.
세로축은 물품을, 가로축은 배낭 용량을 나타낸다.
-
각 물품마다 아래 로직을 반복한다.
- 용량을 1부터 k까지 늘리면서 해당 용량일 때 들어가는 최대 가치를 기록한다.
- 만약 그 용량에 현재 물품이 들어가지 않는다면, 이전에 구했던 최대 가치를 그대로 사용한다.
- 물품이 들어간다면, 다음 두 값 중에서 최대값을 선택한다.
-
- 그 물품의 용량 만큼을 뺐을 때 들어가는 최대 가치와 현재 물품의 가치를 더한 값
-
- 이전에 구했던 최대 가치
참고
소스코드
// 입력 처리
const INPUT_NAME = "i1.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const [n, k] = input[0].split(" ").map(e => Number(e));
const items = input.slice(1, n + 1).map(e => e.split(" ").map(e => Number(e)));
items.unshift([0, 0]);
const dp = Array.from({ length: n + 1 }, () => Array.from({ length: k + 1 }, () => 0));
// 문제
function solution() {
// i번째 물건마다 반복
for (let i = 1; i <= n; i++) {
const [weight, value] = items[i];
// 배낭 용량 j를 1부터 k까지 늘리면서 들어갈 수 있는 가치 최대값 구하기
for (let j = 1; j <= k; j++) {
// 만약 지금 배낭 용량으로는 물건을 넣을 수 없다면, 이전에 현재 배낭 용량일 때 나왔던 최대값이 결과가 된다.
if (j < weight) dp[i][j] = dp[i-1][j];
// 지금 배낭 용량으로 현재 물건을 넣을 수 있다면,
// 이전에 구했던 정보를 참고하여 현재 물건만큼의 용량을 뺐을 때의 최대값과 현재 물건의 가치를 더한값을 가져온다. (현재 물건 넣기)
// 그리고 이전에 현재 배낭 용량일 때 나왔던 최대값과 비교하여 (현재 물건 넣지 않기)
// 현재 물건을 넣는게 최대값이 되는지, 아니면 그냥 넣지 않는게 최대값이 되는지를 저장한다.
else dp[i][j] = Math.max(value + dp[i-1][j-weight], dp[i-1][j]);
}
}
console.log(dp[n][k]);
}
// 실행
solution();