[백준 12865] 평범한 배낭 - 자바

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

12865번: 평범한 배낭

 

1. 풀이

---

DP관련 알고리즘 수업때 항상 나오는 문제인걸로 알고 있습니다. knapsack 알고리즘이라고도 하죠.

 

처음엔 완전탐색(브루트-포스)로 해볼려고 했으나, O(2^n)의 시간복잡도를 가지므로 포기했습니다. 

 

그리디 알고리즘도 가격이나, 무게중 하나를 탐욕적으로 계산을해도 최적의 답은 찾지 못합니다. 즉, DP로 풀어야합니다.

 

DP문제이므로, 순환식을 먼저 찾아야 합니다. 하지만, 아무리 해도 찾지 못해서 구글링을 통해 알게되었습니다.

 

입력으로 받은 물건들을 하나씩 봅니다. 물건을 하나하나 볼 때 그 물건을 무게 0~n까지의 모든 경우에 넣어보고 넣을 수 없다면 이전 물건을 그대로 가져가고, 넣을 수 있다면 비교를 통해 더 큰 것을 가져갑니다.

 

순환식

문제의 예제를 통해 이해해보겠습니다. 4개의 물건이 있고, 최대 중량은 7입니다.

i	W ( 무게 )	V ( 가치 )
1	6	13
2	4	8
3	3	6
4	5	12

위와 같은 입력값을 아래와 같이 만들어 줍니다.

i\w	0	1	2	3	4	5	6	7
0 {}	0	0	0	0	0	0	0	0
1 {1}	0	0	0	0	0	0	13	13
2 {1,2}	0	0	0	0	8	8	13	13
3 {1,2,3}	0	0	0	6	8	8	13	14
4 {1,2,3,4}	0	0	0	6	8	12	13	14

위 표에서 열은 가방의 무게, 행은 물건의 개수를 의미합니다. {1,2,3}은 첫번째, 두번째, 세번째 물건을 사용하는 것을 의미하며, 각각의 무게

 

에 최대 가져갈 수 있는 가치를 표로 정리한 것입니다. 

 

https://www.youtube.com/watch?v=mUFfuzpnLHs&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=57 강의를 보시면 이해가 되실겁니다.

 

2. 풀이

---

import java.util.*;

public class Main {
	
	public static int max(int a, int b) {
		if(a > b)
			return a;
		else
			return b;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int num = sc.nextInt();
		int maxWeight = sc.nextInt();
		int[] w = new int[num+1];
		int[] v = new int[num+1];
		int[][] memo = new int[num+1][maxWeight+1];
		
		// 입력
		for(int i = 1; i <= num; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		
		// DP
		for(int i = 1; i <= num; i++) {
			for(int j = 1; j <= maxWeight; j++) {
				if(w[i] > j)
					memo[i][j] = memo[i-1][j];
				else
					memo[i][j] = max(memo[i-1][j], memo[i-1][j-w[i]]+v[i]);
			}
		}
		
		System.out.println(memo[num][maxWeight]);
		
		sc.close();
		return;
	}
}