[백준 12865] 평범한 배낭, 동적 계획법:Dynamic Programming

문제 소개

[문제]
동적 계획법(Dynamic Programming) 문제다. 무게와 가치가 있는 물건을 한도가 있는 배낭(knapsack)에 넣는 것은 대표적인 동적 계획법 알고리즘 문제이다.

사실 문제 풀이법을 찾아보기 전까지는 동적 계획법을 몰라서 아래처럼 무게 별 가치로 정렬 후 더하는 방식으로 짰다가 바로 틀렸다. (ㅜㅜ) 그리디 알고리즘은 이 경우에 알맞지 않다.

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

class Stuff {
	int weight = 0;
	int value = 0;
	float v_per_weight = 0;

	Stuff(int weight, int value) {
		this.weight = weight;
		this.value = value;
		this.v_per_weight = (float) value / weight;
	}

}

// 클래스 이름은 Main으로 변경해야 함.
public class NolmalBag_12865 {
	public static int conquer(Stuff[] arr, int p, int q) {
		int pivot;
		Stuff tmp;
		int low, high;

		pivot = p;

		low = p + 1;
		high = q;

		while (low < high) {
			while (low <= q && arr[pivot].v_per_weight <= arr[low].v_per_weight) {
				low++;
			}
			while (high > p && arr[pivot].v_per_weight > arr[high].v_per_weight) {
				high--;
			}

			if (low < high) {
				tmp = arr[low];
				arr[low] = arr[high];
				arr[high] = tmp;
			}
		}

		tmp = arr[high];
		arr[high] = arr[p];
		arr[p] = tmp;

		return high;
	}

	public static void quickSort(Stuff[] arr, int p, int q) {
		if (p < q) {
			int pivot = conquer(arr, p, q);
			quickSort(arr, p, pivot - 1);
			quickSort(arr, pivot + 1, q);
		}
	}

	public static void main(String[] args) {
//		N개 물건(W, V), W의 총합<=K, V만큼 즐길 수 있음.
//		V를 최대한 크게해서 총 K무게 안으로 짐을 싸야 함.
//		첫 줄은 물품 수, 준서가 버틸 수 있는 무게

		try {

			BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
			String a = bf.readLine();

			String[] arr = a.split(" ");
			int q = Integer.parseInt(arr[0]);
			int k = Integer.parseInt(arr[1]);
			Stuff[] stuffs = new Stuff[q];

			for (int i = 0; i < q; i++) {
				String pack = bf.readLine();
				String[] WV = pack.split(" ");
				stuffs[i] = new Stuff(Integer.parseInt(WV[0]), Integer.parseInt(WV[1]));
			}

			quickSort(stuffs, 0, stuffs.length - 1);

			int bag_weight = 0;
			int valuse = 0;

			for (Stuff i : stuffs) {

				if (bag_weight + i.weight < k) {
					bag_weight += i.weight;
					valuse += i.value;
				}
			}

			BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

			bw.write(valuse + "\n");

			bw.flush();
			bw.close();

		} catch (IOException e) {
			System.out.println(e.toString());
		}

	}
}

동적 계획법

동적 계획법은 반복되는 부분 문제들의 연산 결과를 어딘가에 저장해 놓고 필요할 때 가져다 쓰는 방법이다.
대표적으로 피보나치 수열이 있는데, 적절한 크기의 피보나치 수열의 해를 재귀호출을 통해 찾다보면 필연적으로 동일한 호출이 발생하게 된다. 이때 동일한 호출의 해를 다시 연산하지 않고 배열에 저장해 놓고 꺼내쓰면 전체 연산 속도가 훨씬 줄어든다.

수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
[위키백과]

동적 계획법의 조건

동적 계획법을 적용하려면 두 가지 속성을 만족시켜야 한다.

예를 들기 위해 피보나치 수열을 보자.

public static int fibo(int n) {
    System.out.printf("fibo(%d)%n", n);
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fibo(n - 2) + fibo(n - 1);
}

부분 문제 반복(Overlappting Subproblem)

fibo(5)를 실행하면 다음이 출력된다.

fibo(5) fibo(3) fibo(1) fibo(2) fibo(0) fibo(1) fibo(4) fibo(2) fibo(0) fibo(1) fibo(3) fibo(1) fibo(2) fibo(0) fibo(1)

보이는 것처럼 fibo(1~3)이 여러번 호출된다. 처음에 입력한 값이 조금만 커져도 연산이 배로 많아져 비효율적이다.
이처럼 부분 문제 반복은 부분 호출 중에 반복되는 부분이 존재하는 것을 의미한다.

최적 부분 구조(Optimal Substructure)

작은 부분 문제에서 구한 최적의 답을 이용해 합쳐진 큰 문제의 최적을 답을 구할 수 있어야 한다는 뜻이다.

return fibo(n - 2) + fibo(n - 1);

피보나치 함수에서 최종 답은 작은 부분 문제의 (최적의)답을 이용하며 도출한다.

메모이제이션(Memoization)

위에서 말한 것처럼 부분문제의 답을 어딘가에 저장해놓고 문제를 풀면서 반복된 호출이 나오면 사용해 효율성을 높이는 방법이다.

피보나치 재귀호출의 메모이제이션 예시:

public class Fibo {

	public static int[] fibo_memo;

	public static int fibo(int n) {
		if (fibo_memo[n] != -1) {
			return fibo_memo[n];
		}
		fibo_memo[n] = fibo(n - 1) + fibo(n - 2);

		return fibo_memo[n];
	}

	public static void run_fibo(int n) {
		fibo_memo = new int[n + 1];

		for (int i = 2; i < fibo_memo.length; i++) {
			fibo_memo[i] = -1;
		}
		fibo_memo[0] = 0;
		fibo_memo[1] = 1;

		System.out.println(fibo(n));
	}

	public static void main(String[] args) {
		run_fibo(10);
	}
}

문제 풀기

이제 문제를 풀어보자.
피보나치 수열에서는 1차 배열이었지만 여기서는 2차 배열을 사용한다. 일반식은 다음과 같다.

$$ V[i, w] = \left\{\begin{matrix}
V[i-1, w] \qquad if (w_{i} > w) \\
max\left\{ v_{i} + V[i-1, w-w_{i}], V[i-1, w] \right\} \qquad else
\end{matrix}\right. $$

$ V[i, w] $에서 $ i $는 물건의 개수, $ w $는 무게 한도이며 이 연산은 저 상황에서 가치의 총합이 가장 클 때의 가치총합을 뜻한다.
$ w_{i} $와 $ v_{i} $는 각각 $ i $번째 물건의 무게와 가치이다.

표를 차례대로 채워나간다고 생각하면 쉽다.

아래 표는 $ V[2, 3] $을 나타내는 표이다. $ i $와 $ w $가 0일 때의 값은 0으로 채우고 나머지 칸들을 순서대로 알아내면 된다.

$ i $/$ w $	1	2	3
0	0	0	0
1	$ V[1, 1] $	$ V[1, 2] $	$ V[1, 3] $
2	$ V[2, 1] $	$ V[2, 2] $	$ V[2, 3] $

더 큰 예시로 직접 해보면 이해가 빠르다.(여기 과정을 서술하진 않겠다.)

위의 식을 다시 한 줄 씩 살펴보자.

$$ V[i-1, w] \qquad if (w_{i} > w) $$

$ i $번째 물건의 무게가 무게한도보다 크면 $ V[i-1, w] $의 값을 채택한다. 현재 가리키는 물건을 넣지 못하니 그것보다 물건이 하나 적었을 때의 최적값을 선택한다는 뜻이다.

$$ max\left\{ v_{i} + V[i-1, w-w_{k}], V[i-1, w] \right\} \qquad else $$

$ i $번째 물건의 무게가 무게한도보다 작으면 다음 두 가지 상황 중에서 더 가치의 총합이 큰 것을 채택한다.

$ v_{i} + V[i-1, w-w_{i}] $

$ i $번째 물건의 가치 + 물건이 $ i-1 $개 일때 무게한도가 현재무게한도 - $ i $인 조건의 최적값.

= $ i $번째 물건을 넣기 위해 이전 최적값들 중에 $ i $번째 물건 무게 만큼의 무게 여유가 있는 최적값을 찾고 거기에 $ i $번째 물건을 넣었을 때 가치의 총 합.

$ V[i-1, w] $

물건이 $ i-1 $개이고 지금과 같은 무게 한도를 가졌을 때의 최적값. $ i $번째 물건을 넣지 않았을 때의 최적값.

요약하면 굳이 $ i $번째 물건을 넣어야 하느냐 말아야 하느냐를 판단하기 위해 둘의 가치를 비교하는 것이다.

답안 코드

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

// 클래스 이름은 Main으로 변경해야 함.
public class NolmalBag_12865 {
	public static int[] weights;
	public static int[] values;
	public static int[][] memo;
    
	public static void knapsack() {
    // memo[0][0]은 실제로 물건개수=0, 무게 한도=0인 경우를 뜻하지만
    // weigths[0]과 values[0]은 i-1번째 물건의 무게, 가치이기
    // 때문에 i에서 1을 빼주어야 함.
		for (int i = 1; i < memo.length; i++) {
			for (int w = 1; w < memo[0].length; w++) {
				if (weights[i - 1] <= w) {
					memo[i][w] = Math.max(values[i - 1] + memo[i - 1][w - weights[i - 1]], memo[i - 1][w]);
				} else {
					memo[i][w] = memo[i - 1][w];
				}
			}
		}

	}

	public static int[] get_inputs() {
		try {

			BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
			String a = bf.readLine();

			String[] arr = a.split(" ");
			int q = Integer.parseInt(arr[0]);
			values = new int[q];
			weights = new int[q];

			int k = Integer.parseInt(arr[1]);
			memo = new int[q + 1][k + 1]; // 기본값으로 0이 들어감

			for (int i = 0; i < q; i++) {
				String pack = bf.readLine();
				String[] WV = pack.split(" ");

				weights[i] = Integer.parseInt(WV[0]);
				values[i] = Integer.parseInt(WV[1]);
			}
			return new int[] { q, k };

		} catch (IOException e) {
			System.out.println(e.toString());
			return new int[1];
		}
	}

	public static void main(String[] args) {
//		N개 물건(W, V), W의 총합<=K, V만큼 즐길 수 있음.
//		V를 최대한 크게해서 총 K무게 안으로 짐을 싸야 함.
//		첫 줄은 N W
//		두 번째 줄부터 각 물건의 W V

		int[] q_k = get_inputs();

		knapsack();

		System.out.println(memo[q_k[0]][q_k[1]]);

	}
}

'Programming > Algorithm' 카테고리의 다른 글

[백준 1655] 가운데를 말해요, 우선순위 큐: Priority Queue, Heap. feat.JAVA (2)	2022.03.19

\( i \)/\( w \)	1	2	3
0	0	0	0
1	\( V[1, 1] \)	\( V[1, 2] \)	\( V[1, 3] \)
2	\( V[2, 1] \)	\( V[2, 2] \)	\( V[2, 3] \)

문제 소개

동적 계획법

동적 계획법의 조건

부분 문제 반복(Overlappting Subproblem)

최적 부분 구조(Optimal Substructure)

메모이제이션(Memoization)

문제 풀기

답안 코드

'Programming > Algorithm' 카테고리의 다른 글

티스토리툴바