[백준 12865] 평범한 배낭/자바/dp **

문제         

레벨: G5
알고리즘: DP ( dp 업데이트 기준 2개 + 이차원 배열)
풀이시간:  1시간
힌트 참조 유무: 유

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

1 번째 시도   

시작에 앞서, 이 알고리즘을 이해하기 힘들 것임을 미리 말한다. 배열에 들어가는 것이 행과 열이 일치하는 값이 아니라 기존까지 구했던 것 중에서 최적의 답, 최대값(누적값)이 들어감을 알아야 한다.


이 문제는 배낭 문제(knapsack)로 매우 유명한 문제다. 문제 설명처럼 배낭에 넣을 수 있는 최댓값이 정해지고 해당 한도 물건을 넣어 가치의 합이 최대가 되도록 고르는 방법을 찾는 것이다. 즉, 조합 최적화 문제다.

 

배낭문제, 일명 냅색 알고리즘은 크게 두 가지 문제로 분류 될 수 있는데, 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우로 나눌 수 있다. 짐을 쪼갤 수 있는 배낭문제를 Fraction Knapsack Problem 이라 하고, 짐을 쪼갤 수 없는 배낭문제를 0/1 Knapsack Problem 이라 한다. 알고리즘 또한 다르게 적용하는데, Fraction Knapsack Problem 의 경우 탐욕 알고리즘(Greedy)을 쓰며, 0/1 Knapsack Problem의 경우 DP 법을 쓴다.

어떤 문제를 DP로 풀기 위해서는 특정 값을 기준으로 현재의 최적값이 과거의 최적값을 통해 설명될 수 있어야 한다. 하지만 이 문제의 경우 기준을 하나만 두어서는 점화식을 만드는 것이 불가능했다. (예 - 가방의 무게가 같더라도 그 안에 넣은 아이템의 종류에 따라 미래의 가치가 달라질 수 있음/ 예제1에서 무게가 6일 때 최대 가치 13(6kg), 무게가 7일 때 최대 가치 14(4kg && 3kg)

해결법은 '조건'을 여러 개로 두는 것, 즉 다차원 배열을 이용하는 것이다.

 

https://jsw5913.tistory.com/130

[백준 2293] 동전1 / 자바 / dp

아래 글을 읽기 전에 위 글을 읽고 왔으면 좋겠다. 참고로 위 문제는 dp배열 업데이트 기준이 1개이고 1차원 배열을 이용한다. 그러나 2차원배열을 이용한 풀이도 보여줬다. 

그렇다면 2차원 배열을 1차원 배열로 축소하는 건 가능할까? 
=> 불가능하다. 동전1에서 1차원배열일 수 있던 이유는 바로 이전 탐색만 참고하면 되기 때문이다. 그러나 '평범한 배낭' 문제는 업데이트 기준이 2개이고 바로 이전 탐색 뿐만 아니라 훨씬 이전의 탐색도 참고해야 하기 때문에 무조건 2차원 배열을 써야 한다. 
=> 아니다. 축소할 수 있다.

 

 

Bottom-Up 방식, 2차원배열

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]);
		}
				
	}
}

코드를 이해하기 앞선 배열에 들어가는 건 가치(열) 해당 가방(행)이 일치한 값이 들어가는 게 아니라 최대값(누적값)이 들어간다는 걸 알아야 이해하기 편하다.

동전1 문제와 비슷하게

가방 1번으로 K = 1, 2,3,4,5,6,7  순서대로 탐색
                 ↓
가방 1,2번으로 K = 1, 2,3,4,5,6,7  순서대로 탐색
                 ↓
가방 1,2,3번으로 K = 1, 2,3,4,5,6,7  순서대로 탐색
                 ↓
가방 1,2,3,4번으로 K = 1, 2,3,4,5,6,7  순서대로 탐색

 

Bottom-Up 방식, 1차원배열

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 방식의 특성상 작은 것부터 맞춰나가기 때문에 dp배열을 2차원이 아니라 1차원으로 생성하고 중복탐색을 피해가는 방식으로 바꿀 수 있다. 어떻게? 생각해보자. 우리가 각 탐색의 경우 i번째 물건에 대하여 W[i]의 합이 K를 넘겨서는 안된다. 이는 거꾸로 말하면 K(최대무게) - 누적된 W값이 0보다 커야한다는 의미다. 즉, 불필요하게 1부터 K까지 탐색하는 것이 아니라 K-W[i] 에 대하여 0보다 크거나 같을 때 까지만 탐색함으로 불필요한 탐색을 줄일 수 있고, 중복 카운트 또한 피할 수 있다.

 

 

정답코드( 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[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]);
	}
}