[백준] 12865번 : 평범한 배낭 - JAVA [자바]

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

---

• 문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

 

이 문제는 배낭 문제(knapsack)로 매우 유명한 문제다. 문제 설명처럼 배낭에 넣을 수 있는 최댓값이 정해지고 해당 한도 물건을 넣어 가치의 합이 최대가 되도록 고르는 방법을 찾는 것이다. 즉, 조합 최적화 문제다.

 

배낭문제, 일명 냅색 알고리즘은 크게 두 가지 문제로 분류 될 수 있는데, 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우로 나눌 수 있다. 짐을 쪼갤 수 있는 배낭문제를 Fraction Knapsack Problem 이라 하고, 짐을 쪼갤 수 없는 배낭문제를 0/1 Knapsack Problem 이라 한다. 알고리즘 또한 다르게 적용하는데, Fraction Knapsack Problem 의 경우 탐욕 알고리즘(Greedy)을 쓰며, 0/1 Knapsack Problem의 경우 DP 법을 쓴다. (물론 FPTAS(Fully polynomial time approximation scheme) 으로 스케일링을 통한 방법도 있지만 근사치를 얻는 방법인지라 자칫 틀릴 수도 있다.)

 

이번 문제는 짐을 쪼갤 수 없기 때문에 다이나믹 프로그래밍(DP)로 해결해야한다.

 

 

이전에 LCS문제를 풀었던 것처럼 한 번 표를 그려보자.

 

먼저 무게 W[] 배열과 가치 V[] 배열이 있다고 할 때, 각 W[i] 의 무게에 대응되는 가치는 V[i]다. 즉, (W_i, V_i) 라고 할 때, 위 예제로는 다음과 같다.

(W_i, V_i) = (6, 13), (4, 8), (3, 6), (5, 12)

그리고 배낭이 수용 가능한 최대 무게 K = 7 이다.

 

이를 토대로 수용가능한 최대 무게에 따른 i까지의 각 물품 및 가치를 표로 그려보면 규칙을 발견할 수 있다. dp(수용가능한 무게)를 0부터 하나씩 채워보도록 하자. (참고로 세로줄은 ~까지 탐색했다는 의미다.)

 

 

 

당연히 dp[0] 은 수용가능한 무게가 0이므로 모두 0일 것이다.. 

 

dp[1], dp[2] 또한 수용가능한 물건이 없으므로 모두 0으로 채우자.

 

 

 

 

 

 

다음부터는 이제 채울 것이 생긴다. 일단 dp[3] 즉, 무게 3을 수용 할 수 있는 것은 i = 3 일 때부터이다. 즉, 아래와 같다.

 

 

 

 

응? 왜 i=4 일 때도 6으로 채워지나요?  라고 묻는다면 앞서 말했지만 세로줄을 ~까지 탐색한다는 의미라고 했다. 즉, i=3에 대해 탐색했는데 무게 3에 대응되는 6을 담을 수 있어 dp[3]에 저장되었다. 그 다음에 i=4를 탐색할텐데, W[4] = 5 이므로 무게가 5라는 의미이므로 채울 수 없고 이전 i=3 에 대하여 탐색할 때의 채워진 값을 그대로 갖고 있게 되는 것이다. (누적 탐색이라 하면 이해가 될려나..)

 

일단 차근차근 채워보면 이해 갈 것이다.

 

그 다음 수용가능한 무게가 4일 때이다. 마찬가지로 i=2 일 때 담을 수 있는 것을 발견할 수 있다.

 

 

 

 

여기서 중요한 포인트 하나.

i = 1부터 탐색할 때, i = 1 일 때에는 (6, 13) 으로 주황색 박스에 있는 칸에 들어갈 수 없다. 즉, 탐색하기 전에 해당 값에 대하여 이전 i값에 대한 dp에 메모이제이션 되어있는 값을 갖고와야한다.

 

현재 수용가능한 무게가 4라면 i 탐색 전에 먼저 이전 i에 대한 값을 갖고와야하는데, i = 0인 경우는 주어지지 않는다. 그렇기 때문에 0이 채워지는 것이다.  그리고 난 후, i = 2 부터는 8을 넣는 것이 최대 가치이므로 8이 차지하게 될 것이다.

 

 

 

다음 줄도 똑같은 방식으로 채운다.

 

 

 

마찬가지로 i = 1, 2, 3번째 열에서는 이전 무게의 값을 갖고있게 될 것이고, i = 4 일 때 새로운 값이 넣어질 것이다.

 

 

마찬가지로,,,

 

 

 

 

 

그리고 7번째가 가장 중요하다. 사실 이전까지는 두 개 이상의 조합으로는 구성할 수가 없었기 때문에 그냥 넘어갔지만, 7부터는 다르다. 한 번 보도록 하자.

 

 

먼저 이전 과정과 마찬가지로 이전의 i값에 대하여 값을 갖고온다. 다만, i = 0 일 때는 주어진 배열 범위 밖이기 때문에 0이 된다.

그리고 i=1 일 때 탐색을 해보자. (W₁, V₁) 은 (6, 13)이었다. 그럼 두 가지 방식으로 구성할 수 있다. 무게가 7인 물건 또는 (무게가 6인 물건 + 무게가 1인 물건) 의 조합을 갖을 수 있다.

 

즉, dp[7 - W[1]] 인 dp[1]의 이전 i값(i=0) 에 대한 값 + W[1]의 가치 = 13과 dp[7]_i=0 = 0을 비교하는 것이다. 즉, 13이 0보다 크기 때문에 13이 저장된다.

 

한마디로 분할하여 무게가 6인 물건(가치=13)과 무게가 1(가치=존재X)인 가치의 합과

무게가 0인 물건의 가치를 비교하는 것이다.

 

 

다음 i = 2일 때이다.

 

 

 

i = 2 는 (4, 8) 이다. 일단 이전 i값인 13을 갖고온다. 그리고 (7 - W[2]) 무게에 대한 이전 i값, 즉 (7 - 4) = 3이고, 3이라는 무게에 대응되는 i = 1 일 때의 값(빨간색 박스)은 0이다 . 이 둘을 합하면 8이 되고, 8과 13 중 최댓값은 13이므로 13이 저장된다.

 

 

 

 

i = 3 일 때도 마찬가지다. 먼저 이전 dp[7] 일 때의 i=2의 값 13을 갖고온다. 그리고 다른 조합방법을 탐색하기 위해 현재 i = 3 은 (3, 6)이고 가치는 6이다. 그리고 (7 - W[3]) = (7 - 3) = 4이고 4에 대응되는 i = 2의 가치는 가치는 8이다. 즉, 6 + 8 = 14가 되고, 이전 i값보다 큰 값이므로 최댓값 14가 저장된다. 즉, 아래와 같다.

 

 

 

 

그 다음도 마찬가지다. 이전 탐색 값 14(dp[7]_i=3) 과 (7 - W[4]) = 2_i=3 값인 0과 V[4] 인 12의 합 12를 비교하면 14가 크므로 14가 저장된다.

 

 

 

i = 4 일 때 가치는 (5, 12) 로 12 이고, (7 - W[5]) = 2로, 2에 대응하는 무게는 0이다. 즉 합은 12이인데, 이전 값 14 보다 작기 때문에 12가 아닌 14가 저장되는 것이다.

 

 

 

이러한 두 가지 원리로 점화식을 만들면 다음과 같이 만들 수 있다.

 

 

f 는 함수 f, k는 위 표에서 dp, W는 입력으로 주어지는 무게, V는 입력으로 주어지는 가치이다.

 

이를 토대로 재귀문(Top-Down 방식)을 만들 수 있다.

 

static int knapsack(int i, int k) {
	// i가 0미만, 즉 범위 밖이 된다면
	if (i < 0)
		return 0;
		
	// 탐색하지 않은 위치라면?
	if (dp[i][k] == null) {
			
		// 현재 물건(i)을 추가로 못담는 경우 (이전 i값 탐색) 
		if(W[i] > k) {
			dp[i][k] = knapsack(i - 1, k);
		}
		// 현재 물건(i)을 담을 수 있는 경우 
		else if (W[i] <= k) {
			// 이전 i값과 이전 i값에 대한 k-W[i]의 값 + 현재 가치(V[i])중 큰 값을 저장  
			dp[i][k] = Math.max(knapsack(i - 1, k), knapsack(i - 1, k - W[i]) + V[i]);
		}
	}
	return dp[i][k];
}

 

W와 V 배열은 N길이로 인덱스가 0 부터 시작하기 때문에 위의 i=0일 때를 약간 수정하여 i < 0으로 고쳐준다. 또한 f(i - 1, k) 의 경우 결국 최소한 한 번은 탐색해야하기 때문에 선제적으로 이전 i값에 대하여 재귀탐색을 해주어야 한다. 그리고 이해하기 편하게 else if() 를 썼지만, 그러지 않고 그냥 else{} 로 바꿔주어도 무방하다.

 

 

 

이를 역으로 Bottom-Up 방식으로 구현한다면 다음과 같다.

 

for (int i = 1; i <= N; i++) {
	for (int j = 1; j <= K; j++) {
				
		// i번째 무게를 더 담을 수 없는 경우 
		if(W[i] > j) {
			dp[i][j] = dp[i - 1][j];
		}
		// i번째 무게를 더 담을 수 있는 경우 
		else {
			dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
		}
				
	}
}

 

 

이 경우 하위 인덱스부터 시작하기 때문에 i-1 에 대하여 자칫 인덱스 범위 밖을 참조하게 될 수 있다. 그렇기 때문에 W, N 은 각각 [N+1] 사이즈로 선언해주어야 한다.

 

그리고 Bottom-Up 방식의 특성상 작은 것부터 맞춰나가기 때문에 dp배열을 2차원이 아니라 1차원으로 생성하고 중복탐색을 피해가는 방식으로 바꿀 수 있다. 어떻게? 생각해보자. 우리가 각 탐색의 경우 i번째 물건에 대하여 W[i]의 합이 K를 넘겨서는 안된다. 이는 거꾸로 말하면 K(최대무게) - 누적된 W값이 0보다 커야한다는 의미다. 즉, 불필요하게 1부터 K까지 탐색하는 것이 아니라 K-W[i] 에 대하여 0보다 크거나 같을 때 까지만 탐색함으로 불필요한 탐색을 줄일 수 있고, 중복 카운트 또한 피할 수 있다.

 

말로하긴 어려우니 일단 아래 코드를 보자. 

for (int i = 1; i <= N; i++) {

	// K부터 탐색하여 담을 수 있는 무게 한계치가 넘지 않을 때까지 반복 
	for (int j = K; j - W[i] >= 0; j--) {
		dp[j] = Math.max(dp[j], dp[j - W[i]] + value[i]);
	}
}

 

Bottom-Up 첫 번째 알고리즘보다 훨씬 간결하다. 반복문 조건식 자체를 j-W[i] >= 0 으로 선언해주면서 i번째 물건에 대해 넣을 수 있는 경우에 한정하여 탐색하는 것이다.

 

 

재귀로는 위와같이 하기 힘들다. Top-Down 방식 자체가 큰 그림에서 작은 단위로 쪼개들어가는 것이라 다른 단위에서 dp에 대해 참조를 할 때 자칫 불완전한 dp값을 참조하여 엉뚱한 값이 최댓값이 될 수 있기 때문이다. 즉, 해결 방법은 브루트포스(Brute Force)로 해야하는데 이는 메모이제이션을 하지 않기 때문에 당연 시간 복잡도가 O(N²) 이 되고, 이 문제에서는 100% 시간초과를 받게 된다.

 

 

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

이번에는 입력방식은 달리하지 않고 위에서 설명한 3개의 알고리즘에 대한 비교를 해볼 것이다. 입력이야 이쯤이면 대부분 BufferedReader을 알고 있기도 하고 성능이 좋은 것을 알고있을 것이니.. 알고있지 않더라도 BufferedReader 대신 Scanner로 바꿔주기만 하면 되니 어렵진 않으리라 본다.

 

 

1 . Top-Down

2. Bottom-Up 1

3. Bottom-Up 2

 

 

 

 

---

• 풀이

- 방법 1 : [Top-Down]

 

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

public class Main {

	static Integer[][] dp;
	static int[] W; // weight
	static int[] V; // value

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		W = new int[N];
		V = new int[N];

		dp = new Integer[N][K + 1];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			W[i] = Integer.parseInt(st.nextToken());
			V[i] = Integer.parseInt(st.nextToken());
		}

		System.out.println(knapsack(N - 1, K));

	}

	static int knapsack(int i, int k) {
		// i가 0미만, 즉 범위 밖이 된다면
		if (i < 0)
			return 0;
		
		// 탐색하지 않은 위치라면?
		if (dp[i][k] == null) {
			
			// 현재 물건(i)을 추가로 못담는 경우 (이전 i값 탐색) 
			if(W[i] > k) {
				dp[i][k] = knapsack(i - 1, k);
			}
			// 현재 물건(i)을 담을 수 있는 경우 
			else {
				// 이전 i값과 이전 i값에 대한 k-W[i]의 값 + 현재 가치(V[i])중 큰 값을 저장  
				dp[i][k] = Math.max(knapsack(i - 1, k), knapsack(i - 1, k - W[i]) + V[i]);
			}
		}
		return dp[i][k];
	}
}

 

 

Top-Down의 가장 정석적인 방법일 것이다.

 

 

 

 

---

- 방법 2 : [Bottom-Up 1]

 

 

 

 

필자가 앞서 맨 처음 알려주었던 Bottom-Up 방식이다. dp[][] 배열을 방법1과 같이 2차원으로 쓴다.

 

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		int[] W = new int[N + 1]; // 무게
		int[] V = new int[N + 1]; // 가치
		int[][] dp = new int[N + 1][K + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			W[i] = Integer.parseInt(st.nextToken());
			V[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= K; j++) {
				
				// i번째 무게를 더 담을 수 없는 경우 
				if(W[i] > j) {
					dp[i][j] = dp[i - 1][j];
				}
				// i번째 무게를 더 담을 수 있는 경우 
				else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
				}
				
			}
		}
		System.out.println(dp[N][K]);
	}
}

 

 

 

크게 어려울 것은 없을 것이다. 다만 인덱스 참조가 벗어나지 않도록 배열 선언 할 때 조심해야 한다.

 

 

 

---

- 방법 3 : [Bottom-Up 2]

 

 

 

 

두 번째 Bottom-Up 방식이다. 무게를 더 담을 수 있는지 여부를 조건삼아 반복문으로 구현하기 때문에 dp[] 배열을 1차원으로 쓸 수 있고 불필요한 탐색을 하지 않기 때문에 성능 개선에 도움이 될 것이다.

 

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		int[] W = new int[N + 1]; // 무게
		int[] V = new int[N + 1]; // 가치
		int[] dp = new int[K + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			W[i] = Integer.parseInt(st.nextToken());
			V[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 1; i <= N; i++) {
			
			// K부터 탐색하여 담을 수 있는 무게 한계치가 넘지 않을 때까지 반복 
			for (int j = K; j - W[i] >= 0; j--) {
				dp[j] = Math.max(dp[j], dp[j - W[i]] + V[i]);
			}
		}
		System.out.println(dp[K]);
	}
}

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

 

채점 번호 : 22624818  -  방법 3 : Bottom-Up 2

채점 번호 : 22624815  -  방법 2 : Bottom-Up 1

채점 번호 : 22624807  -  방법 1 : Top-Down

 

 

시간 차이도 시간 차이지만, 메모리 부분을 보면 역시 일차원 배열을 dp로 두고 하는 방법이 훨씬 좋다.

---

• 정리

 

 

드디어 동적계획법 1 카테고리가 끝났다. 정말 어떻게 설명해야 이해하기 쉬울지 고민하는게 힘든 파트였다. 그나마 팁이라고 한다면 필자가 꾸준히 강조한 '점화식 찾기'를 하라는 것.

일단 점화식만 찾으면 Top-Down방식으로 쉽게 구현이 가능하고 이를 역으로 바꿔 Bottom-Up까지 구현할 수 있다. 그러니 문제를 보고 분석하고 패턴을 찾는 것이 가장 중심이 되어야 할 것이다. 

 

다음 카테고리는 그리디 알고리즘이다. Greedy Algorithm 이라 하는데, 단어 뜻 그대로 욕심(탐욕) 알고리즘이다. 이는 다음 카테고리에서 자세히 알아보도록 하고 혹여 이번 포스팅에서 이해가 되지 않거나 어려운 점이 있다면 댓글 남겨주시면 답변드리겠다.

 

(참고로 FPTAS 방법은 원소간 간격이 충분히 클 때 최적해를 구하는 방법인데, 쉽게 설명하자면 주어지는 W가 {120, 342, 274, 517} 이라고 할 때, 각 무게를 10으로 나눠 {12, 34, 27, 51}을 해도 풀이가 가능하듯이 스케일링을 하는 방법이다. 그러면 각 원소간 거리가 줄어 탐색 시간을 줄일 수 있고 이는 (1-ɛ) * L 을 만족한다. 필자도 이 방식으로 시도해보았으나 테스트케이스마다 스케일링 가능한 값이 모두 달라 사실상 포기했다...)