백준 - 12865. 평범한 배낭

사람들이 흔히 말하는 Knapsack 문제이다.

이 문제를 오랜 기간 풀지 못했는데 해결하기까지의 시행착오를 정리하고자 한다.

 

12865. 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

입출력

 

설명

첫 줄에 물품의 수(N)와 배낭 무게(K)가 주어진다. 이후 각 물건의 무게(W)와 가치(V)가 주어진다.

배낭이 버틸 수 있는 무게(K) 내에서 가장 가치(V)가 높게 물건을 담으면 된다.

 

가치 합의 최댓값을 출력해야 한다.

 

접근

각각의 물건을 담는 경우와 담지 않는 경우로 구분해 더 좋은 결과를 선택하면 된다는 생각에 기반해 풀이를 시작했다.

 

방법 1.

문제를 읽고 위의 접근 방식을 떠올린 후 곧바로 재귀를 활용해 보았다.

 

물건 각각에 대해 담는 경우와 담지 않는 경우로 구분해 모든 상황을 비교했다.

아래는 주요 코드이다.

	static void getAnswer(int weight, int sum, int current) {
		if(weight > K || current == N) {
			return;
		}
		
		answer = Math.max(answer, sum);
		
		getAnswer(weight + arr[current][0], sum + arr[current][1], current+1);
		getAnswer(weight, sum, current+1);
		
	}

 

이는 추상적으로 생각했을 때 물건이 n개일 때 재귀가 2ⁿ회 진행되므로 결과를 반환하기까지 동작이 매우 오래 걸린다.

 

간단하게 그림으로 보면 아래와 같은 방식이다.

 

시간 초과가 발생했다. 물건 개수의 범위가 1 ≤ N ≤ 100인 것을 고려했을 때 당연한 결과이다.

 

 

방법 2.

재귀를 제외하고는 다른 방법이 떠오르지 않아 이후 오랜 기간 이 문제를 손 놓고 있다가 우연히 0/1 knapsack 알고리즘을 보았고 이후 다시 도전했다.

0/1 kanpsack 알고리즘은 DP이기에 단순히 생각했을 때 n²만큼의 연산을 하므로 재귀를 활용한 방법 1보다 훨씬 빠르다.

 

방법 2 설명

각 물건에 대해 담는 경우와 담지 않는 경우를 고려한다는 것은 같다.

다만 여기에 최대 무게에 대한 고려를 추가해 아래와 같은 2차원 배열을 만든다.

 

이 문제의 입력에 대한 2차원 배열은 아래와 같다.

이후 안에 담길 데이터는 해당 경우에 대한 가치의 최댓값이다.

 

예를 들어 첫 번째 물건에 대한 데이터를 담으면 결과는 아래와 같다.

물건 1은 무게가 6이므로 6번 인덱스부터 담을 수 있다. 따라서 1 ~ 5는 값이 0, 6 ~ 7은 값이 13이다.

 

다음으로 두 번째 물건을 담으면 결과는 아래와 같다.

물건 2의 무게가 4이므로 4번 인덱스부터 8의 값을 가진다.

 

그러나 6번 인덱스부터는 값이 다시 13인데

그 이유는 물건 1, 2만 담는 경우, 무게가 6일 때 가질 수 있는 가치의 최댓값이 13이기 때문이다.

 

다음으로 세 번째 물건을 담아보자. 결과는 아래와 같다.

여기서 눈여겨봐야 할 것은 물건을 3까지 담았을 때 무게 7의 결과가 14라는 점이다.

 

값이 14인 이유는 물건 1, 2, 3을 가지고 있을 때 물건 2, 3을 담는 것이 가장 큰 가치를 가지기 때문이다.

 

그리고 이 값은 아래의 연산을 통해 얻을 수 있다.

Math.max(해당 물건을 담지 않을 경우의 최댓값, 해당 물건을 담을 경우의 최댓값)

= Math.max(해당 물건을 담지 않을 경우의 최댓값, 해당 물건의 무게를 뺐을 때의 최댓값 + 해당 물건의 값)

= Math.max(dp[i-1][j], dp[i-1][j - arr[i-1][0]] + arr[i-1][1])

 

즉, 모든 위치에 대해 위의 연산을 진행하면 최선의 경우만 배열에 담긴다.

 

마지막으로 물건 4까지 담았을 때 최종 결과이다.

위의 동작을 거치면 가장 마지막 인덱스에서 답이 도출된다.

 

아래는 주요 코드이다.

	for(int i = 1; i < N+1; i++) {
		for(int j = 1; j < K+1; j++) {
			if(arr[i-1][0] <= j) {
				dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - arr[i-1][0]] + arr[i-1][1]);
			} else {
				dp[i][j] = dp[i-1][j];
			}
		}
	}

 

 

풀이 코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[][] arr = new int[N][2];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
		}
		
		// 1. 해당 물건을 배낭에 넣는 경우
		// 2. 해당 물건을 배낭에 넣지 않는 경우
		int[][] dp = new int[N+1][K+1];
		for(int i = 0; i < N+1; i++) {
			dp[i][0] = 0;			
		}
		
		for(int j = 0; j < K+1; j++) {
			dp[0][j] = 0;
		}
		
		for(int i = 1; i < N+1; i++) {
			for(int j = 1; j < K+1; j++) {
				if(arr[i-1][0] <= j)  {
					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - arr[i-1][0]] + arr[i-1][1]);
				} else {
					dp[i][j] = dp[i-1][j];
				}
                
			}
            
		}
		
		bw.append(dp[N][K] + "");
		bw.flush();
		
	}
	
}