
https://www.acmicpc.net/problem/12865
문제분석
knapsack(냅색) 알고리즘에 대해 처음 배우게 된 문제였다.
DP 방식으로 냅색 알고리즘을 구현하면 된다.
knapsack알고리즘이란?
이 문제를 기준으로 설명하면 다음과 같다.
n번째 물건을 가방에 넣을 때를 보면, 3가지 상황이 존재한다.
1. n번째 물건이 가방 크기보다 큰 경우
2. n번째 물건이 가방 크기보다 작은 경우일 때
2-1. n-1번째 물건을 넣었을 때(n번째 물건을 넣지 않았을 때)가, 어떻게든 n번째 물건을 넣었을때 보다 가치가 큰 경우
2-2. n-1번째 물건을 넣었을 때보다, 어떻게든 n번째 물건을 넣었을때가 가치가 큰 경우
따라서, 2차원 배열 int[N+1][K+1]를 활용한다. 배열의 [n][k]는 가방의 최대 무게가 k일 때, n번째 물건을 확인하여 저 3가지 상황을 거쳐 해당 가방의 최대 가치를 저장한다.
냅색 알고리즘은 bottom-up 방식의 DP로 구현하면 손쉽게 구현이 가능하다. 중요한점은 어떻게든 n번째 물건을 넣었을 때 를 계산할때, column에서 현재 추가할 stuff무게만큼 빼기에 col->row 순으로 2차원 배열을 채워나가야 한다는 것이다.
코드
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[]args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] temp = br.readLine().split(" ");
int N = Integer.parseInt(temp[0]);
int K = Integer.parseInt(temp[1]);
int[][] knapsack = new int[N+1][K+1]; // 인덱스가 N까지, 무게가 K까지여야 함.'가치' 저장함.
int[][] stuff = new int[K][2];//[k][0]은 무게, [1]은 가치
for(int n = 0; n < N; n++){
temp = br.readLine().split(" ");
stuff[n][0] = Integer.parseInt(temp[0]);
stuff[n][1] = Integer.parseInt(temp[1]);
}
for(int i = 0; i < N+1; i++){
Arrays.fill(knapsack[i],0);
}
for(int n = 1; n < N+1; n++){
for(int k = 1; k < K+1; k++){
if(k<stuff[n-1][0]){ // 가방의 최대 무게 k보다, i번째 물건의 무게가 더 무거운 경우 - 물건 더 추가 불가
knapsack[n][k] = knapsack[n-1][k];
}else{ // 추가 가능할 수 있는 경우 - knapsack[i-1][k]과 knapsack[i-1][k-물건 무게]+ 물건 가치 중 최대값
knapsack[n][k] = Math.max(knapsack[n-1][k],knapsack[n-1][k-stuff[n-1][0]]+stuff[n-1][1]);
}
}
}
System.out.println(knapsack[N][K]);
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 3687 성냥개비 (2) | 2025.08.17 |
|---|---|
| [JAVA] 백준 1106 호텔 (2) | 2025.08.16 |
| [JAVA] 백준 1202 보석도둑 (3) | 2025.08.13 |
| [JAVA] 백준 16402 제국 (5) | 2025.08.06 |
| [JAVA] 백준 2608 로마 숫자 (1) | 2025.07.31 |