😀

07. [DP] 0-1 Knapsack

태그

0-1 Knapsack

도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은?

생각할 수 있는 시행착오

1) 모든 경우의 수를 넣어본다 (Brute-Force)

n개의 보석이 있다고 치면, n개 보석으로 만들 수 있는 가능한 부분집합 (power set) 의 수는 2^n개이다. 최악의 경우에 2^n번까지 봐야 하는, 즉 O(2^n) 의 알고리즘은 너무 느리다.

2) 가격이 높은 보석, 혹은 (가격/무게) 의 값이 제일 높은 보석부터 먼저 골라서 넣는다 (Greedy)

아래의 그림을 보자. 가격이 제일 높은 보석을 먼저 고르는 방법을 쓴다고 하면, 오른쪽 아래에 있는 빨간 보석을 먼저 고르고 그 다음 왼쪽에 있는 노란 보석을 고를 것이다. 그럴 경우에 가격의 총합은 16이 된다.

하지만 1, 2, 3, 4의 무게를 선택하였을 때의 가격은 총합은 19가 나오고 단순하게 가격이 높은 greedy한 방법을 고려했을 때 답을 구할 수 없다.

'무게당 가격'을 계산해서 제일 높은 것부터 집어 넣으면 성립할 것 같다는 생각을 할 수 있다. 실제로 위의 그림에서는 그렇게 수행하면 최적의 답이 나온다. 하지만 언제나 그렇지는 않다. 아래의 예시를 보자

이 경우에 '무게당 가격' 순으로 보석을 넣으면 보석1, 보석3이 들어가며 가격의 합은 19이다. 그런데 배낭 무게가 5가 남는다. 보석2를 넣을 수는 없으므로 5는 그냥 쓸데없이 남는 공간이다.

보석2, 보석3을 넣으면 30무게를 가득 채우고 가격의 합이 20이다. 도둑 입장에서 도망갈 때 배낭이 좀 더 무거울 수 있겠지만 어쨌든 문제의 조건은 배낭이 안 터지는 한도 내에서 가격 합을 최대화하는 것이므로 보석2, 3을 가져가는 것이 정답이다.

이처럼 특정한 기준을 정해놓고 그 기준의 값이 가장 높은 순으로 집는 걸 Greedy 알고리즘이라 하는데 0-1 배낭 채우기 문제는 Greedy한 방법으로는 풀 수 없는 문제이다.

Fractional Knapsack 문제는 Greedy로 풀 수 있다. 위 예시에서 보석2를 반으로 잘라서 남은 5kg짜리 공간에 넣으면 그게 최적의 답이 된다

DP의 적용

어떤 문제를 DP로 풀기 위해서는 '최적의 원리' (Principle of Optimality) 가 성립하는지를 확인해야 하는데, 최적의 원리란 다음과 같다.

"어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다."

이 문제에서 이 원리가 성립할까? 집합 A를 n개의 보석들 중에 최적으로 고른 부분집합이라고 가정하자.

•

집합 A가 n번째 보석을 포함하고 있지 않다면, A는 n번째 보석을 뺀 나머지 n-1개의 보석들 중에서 최적으로 고른 부분집합과 같다.

•

집합 A가 n번째 보석을 포함하고 있다면, A에 속한 보석들의 총 가격은 n-1개의 보석들 중에서 최적으로 고른 가격의 합에다가 보석 n의 가격을 더한 것과 같다. (단, n번째 보석을 넣었을 때 배낭이 터지지 않아야 한다)

점화식으로 풀어보면 아래와 같다.

P[i, w] 란 i개의 보석이 있고 배낭의 무게 한도가 w일 때 최적의 이익을 의미한다. 식을 좀 문장으로 풀어보면 이렇다.

•

i번째 보석이 배낭의 무게 한도보다 무거우면 넣을 수 없으므로 i번째 보석을 뺀 i-1개의 보석들을 가지고 구한 전 단계의 최적값을 그대로 가져온다

•

그렇지 않은 경우, i번째 보석을 위해 i번째 보석만큼의 무게를 비웠을 때의 최적값에 i번째 보석의 가격을 더한 값 or i-1개의 보석들을 가지고 구한 전 단계의 최적값 중 큰 것을 선택한다

풀이 과정

i == 0 || w == 0

고려하는 보석이 0개, 배낭에 집어넣는 무게가 0인 상태이다. 모두 0으로마킹한 상태에서 시작한다.

i == 1

i=1인 경우부터 한칸씩 보자. (i, w)가 (1, 1) 인 경우에는 w=1짜리 배낭으로는 아무 보석도 넣을 수 없으므로 0이다. 그 다음 칸, (1, 2) 인 경우에는 이제 1번 보석을 넣을 수 있으니까 V[1, 2] = 3이 된다.

직관적으로는 이렇고, 위의 식을 통해서 보면 '1번 보석의 가치 + V[0, 0]' 의 값과 V[0, 2] 의 값을 비교해서 더 큰 쪽을 가져가게 되는데, 1번 보석의 가치는 3이고 V[0, 0] 과 V[0, 2] 는 둘 다 0이므로 전자를 선택하게 된다.

i == 2

i=2인 경우를 보면, w=2일때는 현재 보고있는 2번 보석 (3kg) 을 넣을 수 없으므로 바로 윗칸의 3을 가져온다 (1번 보석을 넣는다는 뜻). w=3이 되면 2번 보석을 넣을 수 있게 되는데, 1번 보석을 넣었을 때 (바로 윗칸) 랑 2번 보석을 넣을만큼의 공간을 확보하고 2번 보석을 넣었을 때 (즉, 2번 보석의 가치 + V[1, 0]) 를 비교해서 더 가치가 높은 쪽을 선택한다. 그래서 4가 들어간다.

모든 과정 수행 이후

코드 작성

public class FruitNotFoundException extends Exception {
    public FruitNotFoundException(String name) {
        super(name + "에 해당하는 과일은 없습니다.");
    }
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int W = sc.nextInt();
		
		int[] weights = new int[N+1];
		int[] profits = new int[N+1];
		
		for(int i = 1; i <= N; i++) {
			weights[i] = sc.nextInt();
			profits[i] = sc.nextInt();
		}
		
		int[][] D = new int[N+1][N+1];
		
		for(int i = 1; i<=N; i++) {
			for(int w = 1; w <= W; w++) {
				if(weights[i] <= w) { // 해당 보석을 가방에 넣을 수 있다.
					D[i][w] = Math.max(D[i-1][w], profits[i] + D[i-1][w - weights[i]]);
				}else { // 해당 보석을 가방에 넣을 수 없다.
					D[i][w] = D[i-1][w];
				}
			}
		}
	}
}
Java
복사

0-1 knapsack의 1차원 배열 풀이

DP을 bottom-up의 상향식 풀이로 풀었을 때 DP[w]의 값은 DP[w - i] 의 값을 참조하며 채워지게 된다. i번째 보석의 처리를 수행하기 위해서는 i-1번째 보석까지의 처리 결과를 사용해야 하는데 i번째 보석의 처리 과정에서 i - 1 번째 값을 덮어씌운다면 올바른 정답을 구할 수 없다.

따라서 bottom-up 방식을 사용한다면 2차원 배열을 관리해서 사용하지 않는다면 올바른 정답을 구할 수 없다.

하지만 top-down의 하향식 풀이로 푸는 경우엔 위와 같은 문제를 해결할 수 있다.

위처럼 n차원 배열 DP를 n-1 처럼 최적화 하여 사용하는 방식이 플로이드-와샬 알고리즘에도 적용된다.