[Java]배낭 문제(Knapsack Problem)

*배낭 문제(Knapsack Problem)

->배낭 문제는 조합 최적화의 유명한 문제로, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있는 경우, '일정 가치'와 '무게'가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되로록 짐을 고르는 방법을 찾는 문제이다.

※ 조합 최적화란 쉽게 말해 모든 조합의 경우의 수를 고려하지 않고, 최적화하여 조합의 경우의 수를 줄이는 것을 말한다.

->배낭 문제는 두 가지로 나눌 수 있다.

(1) 분할가능 배낭문제(Fractional Knapsack Problem)

->짐을 쪼갤 수 있다는 가정을 둔다. 예를 들어, 물건이 4kg이고 가치가 8이라면 물건을 2kg으로 나눠 가치가 4인 경우로 분할 해 배낭에 담을 수 있다고 생각하면 된다.

->해당 문제는 그리디 알고리즘을 활용하여 해결할 수 있다.

 

(2) 0-1 배낭문제(0-1 Knapscak Problem)

->짐을 쪼갤 수 없다는 가정을 둔다. 예를 들어, 물건이 4kg이고 가치가 8이라면 물건은 분할 불가능하고 그 무게와 가치 그대로 배낭에 담을 수 있다고 생각하면 된다.

->해당 문제는 동적 계획법을 활용하여 해결할 수 있다. 

 

*0-1 배낭 문제(0-1 Knapsack Problem)

->앞서 설명한 바와 같이 물건을 쪼갤 수 없는 경우를 가정하고 배낭에 물건을 담아 얻을 수 있는 최대 가치를 구하는 문제이다. 즉, 물건을 넣거나(1) 빼거나(0)라는 의미를 강조하기 위해 0-1 배낭 문제라는 이름이 붙었다.

※ 0-1 배낭 문제와 다이나믹 프로그래밍 : 앞서 설명한 바와 같이 0-1 배낭 문제는 동적 계획법을 활용하여 문제를 해결할 수 있다. 여기서는 백준의 Gold5 12865 평범한배낭 문제를 예로 들어 알고리즘을 설명하도록 하겠다. 해당 문제 자체가 0-1 배낭 문제를 나타낸다고 보면 된다.

※ 문제 주소 : https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

*백 트래킹을 활용한 풀이

->동적 계획법을 활용하기 전에, 가장 일반적으로 생각해볼 수 있는 방법은 백트래킹 패러다임을 적용해보는 것이다. 물건이 들어있거나, 들어 있지 않거나(부분 집합의 논리)를 바탕으로 모든 경우를 탐색해서 문제를 해결할 수 있다. 아래 코드를 참고해보도록 하자.

import java.util.Scanner;

public class KnapSack_BackTracking {
	static int N, K;
	static int[][] items;
	static int max;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		// 물건 당 첫 번째 열에는 물건의 무게를, 두 번째 열에는 물건의 가치를 저장한다.
		items = new int[N][2];
		for (int i = 0; i < N; i++) {
			items[i][0] = sc.nextInt();
			items[i][1] = sc.nextInt();
		}
		max = 0;

		// DFS 탐색을 활용하여 모든 경우를 고려해본다.
		dfs(0, 0, 0);
		System.out.println(max);
		sc.close();
	}

	private static void dfs(int depth, int weight, int val) {
		// 모든 물건을 확인하였으면 최종 물건의 가치를 확인하고 재귀를 종료한다.
		if (depth == N) {
			// 현재까지의 최대 가치보다 크다면 값 갱신.
			max = Math.max(max, val);
			return;
		}
		// 물건을 포함할 수 있는 경우 포함하고 재귀를 진행한다.
		if (weight + items[depth][0] <= K) {
			dfs(depth + 1, weight + items[depth][0], val + items[depth][1]);
		}
		// 물건을 포함하지 않고 재귀를 진행한다.
		if (weight <= K) {
			dfs(depth + 1, weight, val);
		}
	}
}

->주어진 테스트 케이스를 적용해보면, 가방에 조합이 가능한 모든 경우를 고려해보면서 재귀가 진행되는 것을 확인할 수 있을 것이다. 또한, 모든 경우를 고려하였기 때문에 시간이 충분하다면 정확한 결과를 도출할 것이다.

->하지만 문제는 당연히 시간이다. 이 방식의 경우 물건을 선택하거나, 선택하지 않는 부분 집합의 논리를 사용하기 때문에 O(2^N)의 지수 시간 복잡도를 갖는다. 즉, 문제에서 주어진 것 처럼 N이 100인 경우에는 2^100번 정도의 연산을 진행해야만 문제를 해결할 수 있다! 따라서 코드를 제출해보면 시간 초과가 발생하는 것을 확인할 수 있을 것이다.

 

*동적 계획법을 활용한 풀이(2차원 dp 테이블 사용)

->이번에는 동적 계획법을 사용하여 문제를 풀이해보자. 해당 블로그에 포스팅한 '동적 계획법 접근 방식'을 바탕으로 문제에 접근해보겠다.

※ 참고 : https://sskl660.tistory.com/87

[Java]동적 계획법(Dynamic Programming)

 

1. 문제를 특정한 부분 문제로 생각해보고, 해당 문제를 저장할 dp 테이블을 정의해본다.

(1) 물건 1개를 넣을 때, 각 무게(1 ~ K)당 가질 수 있는 최대 가치는 무엇일까?

->우선 물건은 한 개만 존재한다고 가정해보고, 각 무게당 넣을 수 있는 물건의 최대 가치를 생각해보는 것이다. 예를 들어 테스트 케이스에서 주어진 물건 중 무게가 6이고 가치가 13인 물건에 대해서만 생각해보면 아래 테이블과 같이 생각해볼 수 있다.

1부터 7까지의 무게에서, 무게는 6이고 가치는 13인 물건을 넣을 때 각 무게에서의 최대 가치는?

->우선 무게가 1인 경우, 해당 물건을 넣을 수 없으므로 다음과 같이 테이블을 채울 수 있을 것이다.

->다음으로 무게가 2인 경우도 마찬가지로 물건을 넣을 수 없으므로 다음과 같이 테이블을 채울 수 있다.

->같은 방식으로 무게가 5인 경우까지 0으로 채울 수 있고, 무게가 6이 되는 순간 물건을 넣을 수 있으므로 무게가 6인 경우는 가질 수 있는 최대 가치가 13이 된다.

->다음으로 무게가 7인 경우 역시, 해당 물건을 넣을 수 있으므로 13으로 채워짐을 알 수 있다.

->자, 그러면 이 데이터에서 어떠한 규칙성을 발견할 수 있을까? 물건이 단 한 개만 존재하는 경우에는 단순히 물건을 넣을 수 있으면 가치를 넣고, 넣을 수 없으면 가치를 0으로 두는 규칙을 사용하여 dp 테이블을 완성할 수 있다. 이제 이러한 느낌을 바탕으로 여러 물건이 주어진 경우를 고려해보자.

 

(2) 물건을 1 ~ N개를 넣을 때, 각 무게(1 ~ K)당 가질 수 있는 최대 가치는 무엇일까?

->이번에는 편의상 이해를 돕기 위해, 무게가 3이고 가치가 6인 물건과 무게가 4이고 가치가 8인 문제를 먼저 넣는다는 가정하에 테이블을 갱신해보자. 우선, 무게가 3이고 가치가 6인 물건은 앞의 논리대로 테이블을 채웠다고 생각한다. 그렇다면 아래와 같은 상태일 것이다.

->이제, 무게가 4이고 가치가 8인 물건을 앞선 방식으로 넣어보자. 우선 무게가 1인 경우 물건을 담을 수 없으므로 가치는 0일 것이다. 이는 무게가 3인 경우까지 반복 될 것이다. 그런데 무게가 3이 되는 지점에 0을 채우는 것이 과연 맞을까?

 해당 테이블에 값을 저장하는 기준이 무엇이었는가? 답은 N번째 물건까지 고려할 때, 해당 위치에서 가질 수 있는 최대 가치를 해당 위치에 저장해두는 것이었다. 그렇다면 해당 위치에는 2번째 물건까지 고려했을때, 무게 3에서의 최대 가치가 저장되어 있어야 하는데, 그 값은 0이 아닌 1번째 물건을 넣어서 얻은 6임을 알 수 있다.

 즉, 기존에 사용하던 물건을 넣을 수 있으면 가치를 넣고, 넣을 수 없으면 가치를 0으로 두는 규칙은 활용할 수 없다는 것을 알 수 있다. 따라서 다른 규칙을 생각해보아야 한다. 우선 여기서는, 해당 위치에 물건을 넣을 수 없다면, 이전에 구한 해당 무게에서의 최대 가치를 그대로 가져오면 된다는 것을 파악하였다.

->다음으로, 무게가 4인 경우역시 중요하다. 이번에는 무게가 3인 경우와 달리 2번째 물건을 넣을 수 있다. 즉, 이 경우

에는 현재 물건의 가치와 이전 물건까지 저장했던 해당 무게에서의 가치를 비교하여 더 큰 값을 저장하면 된다는 것을 알 수 있다.

->마찬가지 방식으로 하면 무게 6까지 같은 방식으로 비교하며 값을 채워나갈 수 있음을 알 수 있다.

->자, 이제 무게가 7인 경우가 관건이다. 앞선 방식을 활용한다면 해당 위치에는 8이라는 가치가 들어가야 할 것이다. 하지만 우리는 직관적으로 무게가 7인 경우 첫 번째 물건과 두 번째 물건을 모두 넣을 수 있으므로 해당 위치에는 14라는 가치가 들어가야 한다는 것을 알고 있다. 즉, 기존에 사용하던 규칙에서 조금 수정이 필요함을 알 수 있다.

 동적 계획법은 이전에 구한 최적해를 활용하여 다른 부분 문제의 최적해를 구하는 과정이라고 하였다. 우리는 첫 번째로 한 개의 물건이 존재하는 경우 최적해를 구하는 과정을 살펴보았지만 해당 규칙은 각 부분 문제의 연관성이 없었다. 두 번째로 설정한 규칙에서는 이전 물건에서 구했던 최적해를 활용하여, 현재 물건의 현재 위치에서의 최적해를 구하는데 참고하였지만 예외가 발생하였다. 따라서, 이전 최적해를 어떻게 사용할 지 다시 생각해보아야한다.

 현재 무게를 포함 시키지 않는다면 가방에 수용할 수 있는 무게는 3임을 알 수 있다. 그렇다면 무게가 3인 경우의 최적해를 활용해 볼 수 있지 않을까?라는 물음을 던져볼 수 있을 것이다. 즉, 우리가 비교할 것은 바로 자신의 값이 아닌, 이전 물건까지 고려했던 최적해의 값에 현재 가치를 더한 값과, 이전에 구했던 무게에서의 최적해를 비교하여 최대 값을 구하는 것이다. 아래 그림을 통해 이해해보자.

 결론부터 말하자면 이게 0-1 KnapSack을 푸는 규칙과 저장할 테이블 배열이다. 나머지 부분은 방금 규칙을 바탕으로 채울 수 있다.

 

2. 부분 문제의 관계를 생각하며 점화식을 도출한다.

->위 규칙을 따라 테이블을 완성하면 다음과 같아짐을 확인할 수 있다. 사실 위의 과정에서 규칙성을 파악했다면, 점화식은 그냥 도출되는 것임을 확인할 수 있다.

 구체적으로 점화식을 생각해본다면 테이블의 이름을 dp라고하고, 행을 i, 열을 j로 표시한다면 다음과 같을 것이다.

 여기에서 W는 현재 고려하는 물건의 무게를 의미하고, V는 현재 고려하는 물건의 가치를 의미한다. 

 

3. 점화식을 바탕으로 dp 테이블을 갱신하면서 최종적으로 전체 문제를 해결한다.

->우선 해당 점화식을 적용하기 위해 기저 조건이 필요하고 이 때문에 2차원 dp테이블을 정의 할 때, 인덱스가 0인 경우 패딩을 주어 기저 조건을 만들어 준다. 이 정보들을 바탕으로 테이블을 완성해보면 아래와 같다.

 즉, 물건을 넣지 않은 경우를 생각하여 첫 번째 물건을 담을 때 기저 조건(최적해)을 바탕으로 테이블을 갱신할 수 있도록 설정해주는 것이다.

 아무튼 초기 dp 테이블의 정의에 따라 dp[4][7]의 값은 4번째 물건까지 고려했을때, 무게 7에서의 최대 가치를 의미한다는 것을 알 수 있다. 결론적으로 이 값이 해당 문제(전체 문제)의 최종 해임을 확인할 수 있다.

 

4. 구현

->위 로직을 이해하였다면 구현은 그냥 하면 된다. 로직이 어려운 것이지, 대부분 동적 계획법 코드는 생각만 해내면 점화식을 바탕으로 구현하기 때문에 코드가 깔끔한 장점이 있다!

import java.util.Scanner;

public class KnapSack_DP1 {
	static int N, K;
	static int[][] items;
	static int max;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		// 물건 당 첫 번째 열에는 물건의 무게를, 두 번째 열에는 물건의 가치를 저장한다.
		// 물건이 없는 경우도 고려하여 인덱스가 0인 경우(패딩)를 추가해준다.
		items = new int[N + 1][2];
		for (int i = 1; i <= N; i++) {
			items[i][0] = sc.nextInt();
			items[i][1] = sc.nextInt();
		}
		max = 0;

		// 먼저 i번째 물건의 j번째 무게에서 가질 수 있는 최댓값을 저장할 수 있는 2차원 dp테이블을 정의한다.
		// 이때, 기저 조건을 위해 dp테이블에 인덱스가 0인 경우(패딩)를 추가해준다.
		int[][] dp = new int[N + 1][K + 1];

		// 1번째 물건부터 N번째 물건까지 모두 고려한다.
		for (int i = 1; i <= N; i++) {
			// 무게가 1인 경우부터 무게가 K인 경우까지 모두 고려한다.
			for (int j = 1; j <= K; j++) {
				// 해당 위치에 물건을 넣을 수 없는 경우.
				if (items[i][0] > j) {
					// i - 1번째 물건까지 고려했을때 무게 j에서의 최대 가치(최적해)를 그대로 가져온다.
					dp[i][j] = dp[i - 1][j];
				}
				// 해당 위치에 물건을 넣을 수 있는 경우.
				else {
					// i - 1번째 물건까지 고려했을때 무게 j에서의 최대 가치(최적해)와,
					// i - 1번째 물건까지 고려했을때 무게 j - items[i][0](현재 무게)의 최대 가치(최적해) + items[i][1](현재 가치) 중에서
					// 더 큰 값을 선택한다!
					dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - items[i][0]] + items[i][1]);
				}
			}
		}
		
		// dp[N][K]를 출력한다(dp테이블의 정의에 따르면 N가지 물건을 모두 고려했을때 K무게에서의 최대 가치를 출력하는 것!).
		System.out.println(dp[N][K]);
		sc.close();
	}
}

->이렇게 상황에 따라서 dp테이블을 2차원으로 정의해주어야 할 수도 있다! 또, 구현하는 과정에서 이렇게 규칙성을 찾고 테이블의 종류를 고려한다는 것이 만만치 않은 일임을 몸소 체감할 수 있었을 것이다.

 

*동적 계획법을 활용한 풀이(1차원 dp 테이블 사용)

->앞의 방식으로도 머리가 아프겠지만, 조금 더 나아가서 dp 테이블을 1차원으로 줄여볼 수는 없을까?라는 물음을 바탕으로 코드를 구현해보자.

 

1. 테이블을 갱신하는 과정에서 테이블에서 활용되지 않는 정보는 무엇인가?

->이전 테이블을 다시 참고해본다면, 해당 테이블에서 바로 이전 행(i - 1)을 제외한 그 이전 행들의 정보(1 ~ i - 2)들은 활용되지 않음을 알 수 있다.

단계를 진행할 때 마다, 바로 이전 행만을 참고하고 있음을 알 수 있다.

 

2. 그렇다면 이전 행들을 잘 기억해둔다면, 굳이 2차원 테이블을 만들지 않아도 되지 않을까?

->해당 가정을 기반으로 1차원 dp 테이블을 만들고 이전 행들을 단순히 기억하면서 다음 행을 갱신해보자. 우선 이 문제를 고려하기 위해서는 물건을 넣어보는 순서를 조금 바꿔주어야 한다. 위의 예시에서 첫 번째 물건과 두 번째 물건을 넣는 순서를 바꿔서 생각해보자.

->우선 첫 번째 물건을 넣는 경우이다.

 애초에 2차원 배열이었다면, 빨간색 화살표와 같이 단순히 그 값을 참고하면서 현재 값을 갱신하였을 것이다. 하지만 현재는 dp 테이블이 1차원 배열이기 때문에, 파란색 화살표와 같이 실시간으로 그 값이 갱신될 때 마다 갱신된 값을 참고하면서 값이 변할 것이다. 일단, 이 단계에서는 딱히 문제가 없다.

->그럼 두 번째 물건을 넣는 경우를 살펴보자.

 

 마찬가지로 2차원 배열이었따면, 빨간색 화살표와 같이 그 값을 참고하면서 현재 값을 갱신하였을 것이다. 하지만 현재는 dp 테이블이 1차원 배열이기 때문에, 파란색 화살표와 같이 실시간으로 갱신된 값을 참고하며 그 값이 갱신되는데, 이때 2차원 배열일 때 이전 배열의 인덱스 3에서의 값과 1차원 배열일 때 인덱스 3의 값이 다르다는 것을 확인할 수 있다. 이것이 다르다는 것의 의미는 참고하는 값이 예기치 못한 이유로 변화되었다는 것을 의미하고, 이것은 해당 위치가 이전에 우리가 정의했던 dp 테이블의 정의(해당 위치에서 갖는 최대 가치,  최적해)를 따른다는 것을 보장할 수 없다는 것을 의미한다!

 

3. 이전 행들을 잘 기억하면... 되지 않을까..?

->일단 일반적인 방식으로 무작정 1차원 배열을 갱신하며 기억하면 안된다는 것을 확인하였다. 그렇다면 어떻게 1차원 배열에 그 값을 잘 저장하면 이 문제를 해결할 수 있지 않을까? 결론부터 말하자면 값을 뒤에서 부터 갱신하는 방법을 사용하면 문제를 해결할 수 있다.

->앞선 과정을 똑같이 진행해보자. 우선, 첫 번째 물건을 넣는 경우를 생각해보자.

 다음과 같이 무게를 7부터 시작하여, 앞 배열을 참고해도 결과는 달라지지 않는다는 것을 확인할 수 있다. 어차피 이전 배열은 최적해를 보장하고 있기 때문에, 앞에서 부터 참고하든 뒤에서 부터 참고하든 그 결과는 같다는 의미이다.

->똑같이 두 번째 물건을 넣는 경우를 생각해보자.

이해를 돕기 위해 무게 7부터 차근차근 생각해보겠다. 마찬가지로 2차원 배열을 사용하는 방식이었다면, 빨간색 화살표와 같이 값을 참고할 것이고, 1차원 배열을 사용하는 방식이라면 파란색 화살표와 같이 값을 참고할 것이다.

 마찬가지로  2차원 배열을 사용하는 방식이었다면, 빨간색 화살표와 같이 값을 참고할 것이고, 1차원 배열을 사용하는 방식이라면 파란색 화살표와 같이 값을 참고할 것인데, 앞선 방식과는 다르게 인덱스가 3인 지점이 아직 갱신이 일어나지 않았으므로, 2차원 배열에서 값을 참고하는 것과 같은 상태로 유지되고 있음을 알 수 있다. 즉, 인덱스 6인 지점에 현재까지의 최대 가치인 8이 적절히 들어가는 것을 확인할 수 있다.

 

4. 구현

->위 로직을 이해하였다면 역시 구현은 그냥 하면 된다. 아래 코드를 참고해보자.

import java.util.Scanner;

public class KnapSack_DP2 {
	static int N, K;
	static int[][] items;
	static int max;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		// 물건 당 첫 번째 열에는 물건의 무게를, 두 번째 열에는 물건의 가치를 저장한다.
		// 물건이 없는 경우도 고려하여 인덱스가 0인 경우(패딩)를 추가해준다.
		items = new int[N + 1][2];
		for (int i = 1; i <= N; i++) {
			items[i][0] = sc.nextInt();
			items[i][1] = sc.nextInt();
		}
		max = 0;

		// 먼저 i번째 물건의 j번째 무게에서 가질 수 있는 최댓값을 저장할 수 있는 1차원 dp테이블을 정의한다.
		// 이때, 기저 조건을 위해 dp테이블에 무게가 0인 경우(패딩)를 추가해준다.
		int[] dp = new int[K + 1];

		// 1번째 물건부터 N번째 물건까지 모두 고려한다.
		for (int i = 1; i <= N; i++) {
			// 무게가 K인 경우부터 무게가 items[i][0]인 경우까지 모두 고려한다.
			for (int j = K; j >= items[i][0]; j--) {
				// 해당 위치에 물건을 넣을 수 없는 경우, 1차원 테이블이 딱히 갱신이 되지 않는다.
				// 따라서 2차원 dp 테이블을 사용하는 경우와 달리 분기문이 사라진다.
				
				// 해당 위치에 물건을 넣을 수 있는 경우.
				// i - 1번째 물건까지 고려했을때 무게 j에서의 최대 가치(최적해)와,
				// i - 1번째 물건까지 고려했을때 무게 j - items[i][0](현재 무게)의 최대 가치(최적해) + items[i][1](현재 가치) 중에서
				// 더 큰 값을 선택한다!
				dp[j] = Math.max(dp[j], dp[j - items[i][0]] + items[i][1]);
			}
		}

		// dp[N][K]를 출력한다(dp테이블의 정의에 따르면 N가지 물건을 모두 고려했을때 K무게에서의 최대 가치를 출력하는 것!).
		System.out.println(dp[K]);
		sc.close();
	}
}

->여기서 주의할 점은 1차원 배열을 이용함으로써 물건을 넣을 수 없는 경우 물건을 그대로 가져오는 코드를 생략할 수 있다는 것이고, 또한 그로인해 물건을 넣고 빼는 조건을 제거하였으므로 물건의 무게는 현재 고려하는 물건의 무게를 넣을 수 있는 부분까지만(j >= items[i][0]) 고려해야 한다는 것이다.

->당연하겠지만, 1차원 배열을 사용하기 때문에 메모리의 사용이 적다는 것을 확인할 수 있다. 또한 모든 무게를 고려하지 않는 조건 때문인지 시간도 줄었음을 확인할 수 있다.

위 : 1차원 배열 사용, 아래 : 2차원 배열 사용

->이처럼 몇 가지 로직을 바탕으로 값을 기억하는 방식을 적절히 조절할 수 있다면, dp 테이블은 다양하게 정의할 수 있음을 알 수 있다. 

 

※ 여기까지가 다이나믹 프로그래밍의 정석 예제 중 하나인 0-1 배낭 문제에 대한 설명이다. 어려운게 너무너무너무 당연하기 때문에.. 잘 이해가 안되더라도 주눅들지 말고 끝까지 연습해 보도록 하자. 다음에는 다이나믹 프로그래밍의 또 다른 정석 예제인 LIS와 LCS에 대해서 포스팅하도록 하겠다.