평범한 배낭
https://www.acmicpc.net/problem/12865
평범한 배낭문제는 대표적인 knapsack 문제입니다.
knapsack에 대해 간단하게 설명드리자면
담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제이다.로 설명드릴 수 있습니다.
문제에서 주어지는 조건에 따라 비트마스킹으로도 풀이할 수 있습니다. 이번 글에서는 다루진 않지만 기회가 된다면 다루어보겠습니다.
저는 두 가지 방법으로 풀었습니다.
첫번째는 완전탐색.
두번째는 다이나믹 프로그래밍.
각 방법을 이용한 이유는 다음과 같습니다.
완전 탐색을 이용한 이유는 가장 단순하게 접근하기 위해서 입니다.
알고리즘을 풀때에는 복잡한 생각으로 인해 쉽게 접근할 수 있는 문제의 핵심을 놓치는 경우가 있습니다. 문제를 빠르게 풀 수 있는 기회를 놓치는 것을 방지하기 위해 단계적으로 접근하고자 가장 단순하게 풀어보았습니다. 또 다른 이유는, 가장 단순한 방식도 연습하지 않으면 구현하지 못하기 때문입니다. 때문에 연습삼아 완전탐색으로 시작했습니다.
다이나믹 프로그래밍으로 접근한 이유는 완전탐색과 관련이 있습니다. 탑다운 방식의 다이나믹 프로그래밍은 완전탐색의 형태와 매우 유사합니다. 즉 완전탐색으로 먼저 풀이가 가능한 문제라면 탑다운 방식의 다이나믹 프로그래밍으로 변환하여 풀이가 가능할 확률이 높습니다. 이러한 점은 점화식이 직관적으로 이해하기 쉽다는 장점이 있지만, 스택구조로 이루어져 있기 때문에 메모리 사용량에 대한 한계가 있습니다. 대략 1만번 깊이 이상은 대부분의 문제에서 요구하는 메모리 사용량에 벗어나므로 주의해야 합니다.
각설하고 각 방법으로 해결한 코드와 풀이 방법에 대해 설명하겠습니다.
public class Main {
static final int INF = -999_999_999;
static int n, k, max;
static int[][] stuffs;
static int find(int depth, int w, int v){
if(w > k)
return INF;
if(depth == n)
return v;
max = Math.max(max, Math.max(find(depth + 1, w + stuffs[0][depth], v + stuffs[1][depth]), find(depth + 1, w, v)));
return max;
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
stuffs = new int[2][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
stuffs[0][i] = Integer.parseInt(st.nextToken());
stuffs[1][i] = Integer.parseInt(st.nextToken());
}
System.out.println(find(0, 0, 0));
}
}위 코드는 완전탐색 방식으로 구현한 코드입니다.
핵심인 find함수에 대해서만 설명하겠습니다.
find함수의 목적은 K라는 무게를 넘지 않은채 최대 물건의 가치 합을 구하기 위한 함수입니다.
이를 위해서는 각 물건의 순서에 맞게 두 가지 경우를 모두 따져보아야합니다.
첫번째는 n번째 물건을 넣는 경우.
두번째는 n번째 물건을 넣지 않는(혹은 못 넣는) 경우.
두 가지 경우 중 최대값을 찾기 위해서 각 경우를 비교하고 마지막으로 가능한 경우의 수 중 가장 큰 값을 반환하면 됩니다.
정확한 값을 도출하기 위해서 예외 조건 두 가지를 넣었습니다.
첫번째는 현재의 무게가 정해진 K를 넘지 않는 것입니다.
이는 문제에서 제시하는 조건을 위배하기 때문에 잘못된 값을 도출할 가능성이 생기게 됩니다.
두번째는 현재의 인덱스(코드에서는 depth)가 주어진 물건의 수를 넘어가는 것을 방지하기 위함입니다.
즉 indexOutOfError를 방지하기 위함입니다.
여기서 중요한 점은 위 조건의 순서입니다.
만약 첫번째 조건이 아닌 두번째 조건이 먼저 오게 된다면 현재의 무게가 K를 넘더라도 마지막 문건이 끝났다고 판단하여 잘못된 경우를 정상적인 경우로 오인하게 됩니다.
때문에 예외 조건도 순서를 고려하여 풀이해야 합니다.
public class Main {
static final int INF = -999_999_999;
static int n, k;
static int[][] stuffs;
static int[][] dp;
static int find(int depth, int w){
if(w > k)
return INF;
if(depth == n)
return 0;
if(dp[depth][w] != INF)
return dp[depth][w];
dp[depth][w] = Math.max(find(depth + 1, w), find(depth + 1, w + stuffs[0][depth]) + stuffs[1][depth]);
return dp[depth][w];
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
stuffs = new int[2][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
stuffs[0][i] = Integer.parseInt(st.nextToken());
stuffs[1][i] = Integer.parseInt(st.nextToken());
}
dp = new int[n][100_001];
for (int i = 0; i < n; i++) {
Arrays.fill(dp[i], INF);
}
System.out.println(find(0, 0));
}
}위 코드는 다이나믹 프로그래밍 방식입니다.
보시는 것처럼 find함수의 형태와 큰 변화가 없습니다.
논리도 완전탐색과 유사합니다.
딱 하나가 추가되었는데, 그것은 이미 계산한 경우의 수를 걸러내기 위해 dp변수가 초기화 되지 않은 값으로 설정되어있는 경우, 이미 최적의 값을 찾았다고 판단하여 해당 dp값을 바로 반환하는 것입니다.
저 같은 경우는 INF라는 상수를 999_999_999으로 설정하였으며, 현재 문제에서 최대값을 구하는 것이 목적이라 -를 붙여 가장 작은 값으로 만들었습니다.
자바에는 Integer.MAX_VALUE가 주어져 정수의 최대값을 쉽게 설정할 수 있지만, 간혹 문제에 따라 Integer.MAX_VALUE에 더하기가 되는 다이나믹 프로그래밍 문제가 존재합니다. 이런 경우 정수 최대값 + 1 == Overflow가 발생하기 때문에 저는 999_999_999로 설정합니다.
dp배열을 2차원 배열로 선언하고 n, 100_001의 크기로 각각 설정했습니다.
그 이유는 W, V로 설정하기에 둘 다 최대 범위가 10만으로, 10만 * 10만은 1백억이 됩니다. 메모리가 버티지 못합니다.
그렇다면 사용하기 좋은 값을 찾아야하는데, 그 힌트는 완전탐색 코드에 존재합니다.
바로 depth, w, v입니다. w와 v는 함께 사용하지 못하므로 (depth, w) 혹은 (depth, v)를 사용해야 합니다.
그리고 이 문제에서 구해야하는 값은 최대 합의 v이기 때문에 v는 dp의 저장변수로 사용하지 못합니다.
결국 (depth, w)만 남게 되면서 dp변수의 저장변수로 사용하게 되었습니다.
해당 문제를 풀면서 가장 시간을 많이 잡아먹은 것은 예외조건의 순서를 설정하는 것이었습니다. 아무런 문제가 없다고 생각하여 앞서 말씀드린 순서를 반대로 설정하게 되었습니다.
찾아본 반례는 모두 통과했는데, 1%에서 틀리게 되어 애꿎은 다른 부분만 수정하다가 30분 이상 시간을 소요했습니다.
제가 잘못된 부분을 찾을 수 있던 반례와 해당 질문게시판 링크를 남기며 글 마치겠습니다.
모두 행복하세요~
입력
5 10
9 5
4 8
8 9
7 8
5 3
정답
11
