[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]다. 즉, (Wi, Vi) 라고 할 때, 위 예제로는 다음과 같다.

(Wi, Vi) = (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 일 때 탐색을 해보자. (W1, V1) 은 (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]) = 2i=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(N2) 이 되고, 이 문제에서는 100% 시간초과를 받게 된다.

---

풀이 및 코드

- 방법 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];
	}
}

- 방법 2 : [Bottom-Up 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[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]);
	}
}