[백준 12865] 평범한 배낭 (JAVA)

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

이번 포스팅에서는 대표적인 동적프로그래밍 문제인 냅색 문제를 다뤄보도록 하겠다.

 

냅색문제는 가방이 있고, 그 가방에 넣을 물건의 가치와 무게가 각각 주어질 때

가방이 수용 가능한 무게에서 물건을 넣었을 때의 최대 비용을 구하는 것이다.

 

 

이 문제를 풀 때의 핵심 아이디어는 

현재 가방의 용량이 j이고

첫번째 물건부터 시작해서 i 번째 물건을 넣고 빼고 했을때의 최대 비용을 기억한다는 것이다.

 

$$f(i,j) = (1,i) 물건들, 가방의 용량 : j, 최대 비용$$

 

f(i,j)를 위와 같이 정의를 내린다고 한다면,

 

하나의 점화식을 세울 수 있다.

 

$$f(i,j) = max( f(i - 1, j), f(i - 1, j - i번째 물건의 무게) + i번째 물건의 가치)$$

 

즉, 가방의 용량이 j일때 1번부터 i - 1 번째 물건을 넣고 빼고 했을 때의 최대 비용과,

가방의 용량이 j - i번째 물건의 무게 일 때 에서 i 번째 물건을 넣었을 때의

최대 비용을 비교한 최댓값이 f(i,j) 가 된다는 것이다.

 

정리하자면, i번째 물건을 넣지 않았을때까지 >> i - 1 까지의 최대 비용과

i번째 물건을 넣게 될경우의 최대 비용을 비교하여 최대 비용을 갱신하는 것이다.

 

이 과정을 반복해서 f(모든물건의 수, 가방의 용량)을 구한다면 그게 답이 될것이다.

 

그럼 점화식도 나왔으니 이 문제를 3가지 방법으로 풀어보도록 하겠다.

 

기본적인 원리는 상단에서 유추한 점화식을 따른다.

 

먼저 가방의 용량이 1일때부터 순차적으로 검사해 최대비용을 얻는 방법이다.

 

전제 물건의 개수를 n, 가방의 최대 용량을 k라고 하고

물건의 무게와 가치를 저장할 이차원 배열과,

상단의 점화식을 통해 얻어낸 값을 저장할 이차원 배열을 선언하도록 하겠다.

 

	static int n,k;
	
	static int[][] things, dp;

 

 

물건은 0번째 행에는 물건의 무게, 1번째 행에는 물건의 가치를 저장할것이다.

따라서 점화식을 코드로 표현한다면 다음과 같이 쓸 수 있을 것이다.

 

dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - things[0][i]] + things[1][i]);

 

그리고 입력받은 크기와 개수에 따라 메모리를 할당받을 메소드도 하나 만들어 주겠다.

 

	static void clear() {
		things = new int[2][n + 1];
		dp = new int[n + 1][k + 1];

	}

 

 

그럼 바로 반복문을 통해 최대 비용을 구하는 메소드를 작성해보겠다.

 

유추해낸 점화식은 가방의 용량보다 현재 넣으려는 물건의 무게가 커서는 안되므로

해당 경우엔 이전 물건까지의 최대 비용을 저장할수 있도록 한다.

 

	static int knapsack() {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= k; j++) {
				if(j >= things[0][i]) {
					dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - things[0][i]] + things[1][i]);
				}else {
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
		return dp[n][k];
	}

 

 

이제 순차적으로 입력을 받아 물건의 무게와 가치를 저장한 후 최대비용을 구하는 메소드를 실행시켜주면

답을 구할수 있다.

 

두번째 방법은,

 

이전엔 가방의 용량이 1일때부터 순차적으로 탐색했다면,

이번에는 역순으로 최대가방의 용량이 최대일때부터 탐색하며 값을 갱신해 나가는 방법이다.

 

이 경우 가방의 용량이 k가 최대 일때,

 

$$f(k) = max(f(k), f(k - i번째 물건의 무게) + i번째 물건의 가치)$$

 

로 표현이 가능하다.

 

문제의 예제로 분석해보자면,

 

물건의 수가 4개 가방의 용량이 7일때,

 

물건이 다음과 같이 주어질 경우

 

물건 번호	물건 무게	물건 가치
1	6	13
2	4	8
3	3	6
4	5	12

 

첫번째 물건을 넣어 확인할때의 최대비용은 다음과 같다.

 

가방 용량	7	6	5	4	3	2	1
최대 비용	13	13	0	0	0	0	0

 

그리고 두번째 물건을 넣어 확인 할 때의 최대 비용은 다음과 같다.

두번째 물건의 무게는 4이므로 현재 가방의 용량 3일때 가치는 0이고 두번째 물건의 가치는 8이므로

가방용량 7일때,6일때의 최대 비용은 갱신 되지 않고 5일때, 4일때만 갱신된다.

 

가방 용량	7	6	5	4	3	2	1
최대 비용	13	13	8	8	0	0	0

 

그리고 세번째 물건을 넣어 확인 할 때의 최대 비용은

 

가방 용량	7	6	5	4	3	2	1
최대 비용	14	13	8	8	6	0	0

 

세번째 물건의 무게는 3이므로 가방 용량 4일때에서 세번째 무게를 넣었을 때 최대 비용이 갱신된다.

 

그리고 네번째 물건을 넣었을때에는 네번째 물건의 용량은 5 이고 가방용량이 2일때 가치는 0 이므로 갱신되지 않고

가방 용량이 0일때 물건을 넣을경우에 더 최대 비용을 가지므로 가방용량이 5일때만 갱신 된다.

 

가방 용량	7	6	5	4	3	2	1
최대 비용	14	13	12	8	6	0	0

 

이런 과정을 통해 가방 용량 7일때의 최대가치가 14임을 알아 낼 수 있는 것이다.

 

이를 코드로 나타낸다면 다음과 같이 작성할 수 있다.

 

	static int knapsack2() {
		for(int i = 1; i <= n; i++) {
			for(int j = k; j >= 1; j--) {
				if(j >= things[0][i]) {
					dp2[j] = Math.max(dp2[j], dp2[j - things[0][i]] + things[1][i]);
				}
			}
		}
		return dp2[k];
	}

 

마지막으로 세번째 방법은

어차피 처음 물건부터 순차적으로 탐색하기 때문에 입력받으면서 탐색을 하는 것이다.

 

알고리즘은 동일하고

입력받는 값을 굳이 저장해 다시 반복문을 사용하기 보단 바로 반복문으로

탐색하는 것이다. 이를 코드로 작성하면 다음과 같이 작성할수 있다.

 

	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[] dp = new int[k + 1];
		
		for(int i = 1; i <= n; i++) {
			st = new StringTokenizer(in.readLine()," ");
			int w = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			for(int j = k; j > 0; j--) {
				if(j >= w) {
					dp[j] = Math.max(dp[j], dp[j - w] + v);
				}
			}
		}
		
		in.close();
		
		System.out.print(dp[k]);
	}