12865번: 평범한 배낭
대표적인 0 - 1 배낭 문제이다.
물건 N개와 배낭의 크기인 K가 주어지고 2번째 줄부터 물건의 가치와 무게가 주어진다.
이때 최대 가치를 구하는 문제다.
4 7
6 13
4 8
3 6
5 12
문제와 같이 예제가 주어졌을 경우 최대 담을 수 있는 물건은 4개 배낭의 최대 사이즈는 7이된다.
이에 맞는 배열을 준비하면 dp = new int[5][8]
이 된다. 물건과 사이즈는 0이 될 수 없으므로 +1씩 해줬다.
dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,0,0]
dp[2] = [0,0,0,0,0,0,0,0]
dp[3] = [0,0,0,0,0,0,0,0]
dp[4] = [0,0,0,0,0,0,0,0]
위와 같이 dp 배열이 초기화되어 있을 것이다. 여기서 열은 무게를 행은 물건의 개수를 나타낸다.
첫 번째, 물건을 확인해보자.
이 물건의 무게는 6이고, 가치는 13이다. 이 물건을 담기 위해서는 최소 6칸의 공간이 필요하다.
따라서 0 ~ 5의 공간에는 담을 수 없다. 6번 인덱스에 해당 물건을 담는다.
dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,13,0]
dp[2] = [0,0,0,0,0,0,0,0]
dp[3] = [0,0,0,0,0,0,0,0]
dp[4] = [0,0,0,0,0,0,0,0]
위와 같이 6번 인덱스에 물건의 가치인 13을 담았다. 7번 인덱스 부터는 6번인덱스에서 물건을 담았기 때문에 해당 가치가 유지된다.
dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,13,13]
dp[2] = [0,0,0,0,0,0,0,0]
dp[3] = [0,0,0,0,0,0,0,0]
dp[4] = [0,0,0,0,0,0,0,0]
두 번째 물건은 무게가 4이고 가치가 8이다. 4번인덱스 이전에는 해당 물건을 담을 수 없다. 4번 인덱스에는 물건을 넣을 수 있다. 또한 5번 인덱스 역시 가치가 유지된다.
dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,13,13]
dp[2] = [0,0,0,0,8,8,0,0]
dp[3] = [0,0,0,0,0,0,0,0]
dp[4] = [0,0,0,0,0,0,0,0]
그러나 6번 인덱스 역시 물건을 담을 수 있다. 그러나 이전 물건을 담았을 때의 가치가 더 크다. 따라서, 이전 물건의 가치로 채워준다.
7번 역시 마찬가지다.
dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,13,13]
dp[2] = [0,0,0,0,8,8,13,13]
dp[3] = [0,0,0,0,0,0,0,0]
dp[4] = [0,0,0,0,0,0,0,0]
세 번째 물건을 보면 무게는 3이고 가치는 6이다. 다시 채워보자.
dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,13,13]
dp[2] = [0,0,0,0,8,8,13,13]
dp[3] = [0,0,0,6,8,8,13,0]
dp[4] = [0,0,0,0,0,0,0,0]
4 ~ 6번까지는 무게가 더 큰 이전 인덱스의 값으로 채워줬다. 하지만 7번 인덱스의 경우에는 이전 물건까지 체크해봤을 때. 현재 무게를 뺀 가치 즉, dp[2][4]
(8) 에 현재 물건을 넣었을 때 증가하는 가치(+6), 14가 이전 물건까지 체크했을 때 7번 인덱스의 최댓값 13보다 크다. 따라서, 14를 채워준다.
dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,13,13]
dp[2] = [0,0,0,0,8,8,13,13]
dp[3] = [0,0,0,6,8,8,13,14]
dp[4] = [0,0,0,0,0,0,0,0]
그렇다면 아래와 같이 점화식을 세울 수 있다.
dp[현재 물건][현재 사이즈]에 대하여
현재 물건의 사이즈보다 현재 체크하는 공간의 사이즈가 작다면?
dp[현재 물건][현재 사이즈] = dp[이전 물건][현재 사이즈]
크다면?
dp[현재 물건][현재 사이즈] = max(dp[이전 물건][현재 사이즈], dp[이전 물건][현재 사이즈 - 현재 물건 사이즈])
물건의 무게를 w, 가치를 v라고 하면 이를 코드로 나타내면 다음과 같다.
for(int i = 1; i < N + 1; i++){
for(int j = 1; j < K + 1; j++){
if(j < w){
dp[i][j] = dp[i - 1][j];
} else{
dp[i][j] = Math.max(dp[i - 1][j], v + dp[i - 1][j - w];
}
}
}
전체 코드
import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int[][] dp;
static int N, K;
public static void main(String[] args) throws IOException {
// System.setIn(Files.newInputStream(Paths.get("src/input.txt")));
// BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
dp = new int[N + 1][K + 1];
for (int i = 1; i < N + 1; i++) {
st = new StringTokenizer(br.readLine());
int w = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());
for (int j = 1; j < K + 1; j++) {
if (j < w) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], v + dp[i - 1][j - w]);
}
}
}
bw.write(dp[N][K] + "");
bw.flush();
bw.close();
br.close();
}
}
'Problem Solving > 백준' 카테고리의 다른 글
13913 : 숨바꼭질 4 Java (0) | 2024.01.12 |
---|---|
1202 : 보석 도둑 - Java (0) | 2024.01.08 |
1106 : 호텔 Java (0) | 2024.01.07 |
30869 : 빨리기다리기 Java (0) | 2023.12.18 |