12865 평범한 배낭

 

 

1. 배낭 문제 알고리즘

 

배낭 문제 알고리즘을 이용해서 풀면 된다.

 

배낭 문제 : 배낭에 담을 수 있는 무게의 최댓값이 정해져 있을 때,

일정한 가치, 무게가 정해져 있는 짐들을 배낭에 담아야 한다. 

이 때 가치의 합이 최대가 되도록 짐을 고르는 방법

 

두 가지로 분류 할 수 있는데,

 

1) 물건을 쪼갤 수 있는 배낭 문제 => 가치가 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는 방식

                                                      => 그리디 알고리즘 사용

 

2) 물건을 쪼갤 수 없는 배낭 문제 => dp를 활용해서 해결

 

 

2. 문제 풀이

 

 

이 예제는 물건을 쪼갤 수 없는 배낭 문제로 dp를 활용한다.

 

문제 예제를 가지고 설명하겠다.

 

4 7
6 13
4 8
3 6
5 12

 

물품의 수(N) : 4

배낭에 넣을 수 있는 최대 무게(K) : 7

item 배열의 0열에는 각 물건의 무게, 1열에는 물건의 가치를 입력하겠다.

=>

 

물건 무게             물건 가치

item[1][0] = 6       item[1][1] = 13  

item[2][0] = 4       item[2][1]= 8 

item[3][0] = 3       item[3][1] = 6

item[4][0] = 5       item[4][1] = 12

 

그러면 dp 를 이용해서 풀이한다.

 

dp[i][j] = 0~i번째 물건 중 1개 이상 선택해서 그 무게 합이 j가 되었을 때

선택한 물건들로부터 얻는 최대 가치

 

즉, 예제에서

1번째 물건의 무게와 가치 :  6 13 

2번째 물건의 무게와 가치 : 4 8

3번째 물건의 무게와 가치 : 3 6 

4번째 물건의 무게와 가치 :  5 12

 

0번째 물건은 없기 때문에 얻을 수 있는 가치도 없다.

=> dp 배열의 0 행렬은 모두 0이다.

 

역시, 물건들을 선택해서 그 무게의 합이 0이 되게 만들 수 없으므로 얻을 수 있는 가치도 없다.

=> dp 배열의 0열은 모두 0이다.

 

 

1) 1행

 

그러면 이제 1행을 생각해보자.

dp[1][1] = 0~1번째 물건으로 1의 무게를 만들었을 때 얻을 수 있는 최대 가치

예제에서 주어진 물건의 무게는 6,4,3,5 이므로 1의 무게를 만들 수 없다.

따라서 그 가치도 0이다.

 

그러다가 dp[1][6] 이 되었을 때는

0~1번째 물건으로 6의 무게를 만들 수 있게 된다.

첫번째 물건의 무게가 6이며 그 가치가 13이다.

=> dp[1][6] = 13

 

dp[1][7] 은 0~1번째 물건으로 7의 무게를 만들어야 한다.

그러면 일단 첫번째 물건으로 6의 무게를 만든다.

그런 다음 1만큼의 무게가 남아 있는데, 위 표에서 보면 무게 1의 최대 가치는 0이다.

따라서 무게 6의 물건 가치 13에 무게 1의 물건 가치 0을 더해서 13 이 된다.

 

이때, dp[0][7] = 0 과 위의 13 값 중 더 큰 수, 즉 13이 dp[1][7] 이 된다.

이에 대한 설명은 아래에서 자세히 하겠다.

 

2) 2행

 

 

역시 3열까지는 dp 값이 0이다가,

4열이 되면,

dp[2][4] = 0~2 번째 물건 중 선택해서 무게 4를 만들었을 때 최대 가치

 

예제에서 첫번째 물건은 무게가 6이기 때문에 안되고,

두번째 물건은 무게가 4이다.

그리고 그 가치가 8이므로

dp[2][4] = 8

 

 

dp[2][5] 역시 8이다.

 

 

dp[2][6] = 0~2번째 물건 중 선택해서 무게 6을 만들었을 때 최대 가치인데

첫번째 물건의 무게가 6이고, 그 가치는 13이다.

두번째 물건의 무게는 4이고, 그 가치는 8이다.

 

그럼 이 문제에서 사용되는 dp 식을 자세히 설명하겠다.

 i = 물건, j = 무게를 의미한다.

 

1.  j 가 item[i][0] 보다 크거나 같을 경우

 

이 경우는 가방에 넣을 수 있는 무게가 j인데,

i번째 물건의 무게 (item[i][0]) 가 이보다 작거나 같아서,

j - (i번째 물건의 무게) 만큼 다른 물건으로 채워 넣는 경우이다.

 

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

 

 

2.  j 가 item[i][0] 보다 작을 경우 

 

이 경우는 가방에 넣을 수 있는 무게 (j) 보다 

i번째 물건의 무게 (item[i][0]) 가 커서 i번째 물건을 넣지 못한다.

그래서 i-1번째의 dp값으로 i번째 dp값을 채워넣는 경우이다.

 

=> dp[i][j] = dp[i-1][j]

 

dp[2][6] 은 두가지 경우 중 첫번째에 해당한다.

그래서 

dp[2][6] = Math.max(dp[1][6], item[2][1] + dp[1][2]) = Math.max( 13, 8+0) = 13 

 

 

3. dp[2][6] = Math.max(dp[1][6], item[2][1] + dp[1][2])  설명

 

1) 

 

위의 식에서 dp[1][6] 이 어떻게 나왔을지 생각해보자.

일단 식 dp[2][6] 에서

0~2번째 물건 중 선택해서 무게 6을 만들어야 한다.

 

첫번째 물건의 무게와 가치 :  6 13

두번째 물건의 무게와 가치 : 4 8

 

이때 첫번째 물건의 무게가 6이므로 이를 사용하면 된다.

이 가치는 13이 된다.

그런데 이 가치는 dp[1][6]에서 구했다.

그렇기 때문에 dp[2][6]에서 이를 사용하는 것이다.

 

2)

 

item[2][1] + dp[1][2] 

이 부분이 어떻게 나왔을지 생각해보자.

 

첫번째 물건 말고도 두번째 물건을 사용해서 무게 6을 만들 수 있다.

즉, 두번째 물건은 무게가 4이고, 그 가치는 8이다.

따라서 item[2][1] = 8 을 더하는 것이고

 

6-4=2 만큼의 무게를 더 채워야 한다.

그런데 위의 그림에서 무게 2의 가치는 0임을 알 수 있다.

그리고 그 값을 dp[1][2] 로 나타내었다.

 

그러면 dp[0][2], dp[2][2] 도 있는데 dp[1][2] 를 사용한 이유가 있을 것이다.

dp는 최대 가치를 찾고 있는 것이기 때문에, 무게 2의 가치도 최대값을 찾아야 한다.

그렇기 때문에 dp[0][2] 보다는 dp[1][2] 가 더 값이 크다.

 

왜냐하면 dp[0][2] 는 0번째 물건만 사용해서 2의 무게를 만들었을 때 최대 가치이고,

dp[1][2] 는 0~1번째 물건 중 선택해서 2의 무게를 만들었을 때 최대 가치이다.

즉 선택지가 더 많다. 그래서 그 값이 더 크다.

 

그러면 dp[2][2]가 dp[1][2]보다 더 클 가능성이 있다.

그런데, dp[2][2]는 0~2번째 물건 중 선택해서 2의 무게를 만들었을 때 최대가치인데,

 

 item[2][1] + dp[1][2] 

이 식에서 알 수 있듯이,

item[2][1] 에서 이미 2번째 물건을 사용했다.

따라서 2번째 물건 제외 0~1번째 물건 중 선택해서 2의 무게를 만들어야 하기 때문에

dp[1][2] 가 되는 것이다.

 

 

 

 

3) 3행, 4행

 

 

위에서 설명한 대로 채우면 된다.

 

 

 

 

 

4) 

 

위에서 dp 식이 두가지 있었다.

그 중에서 첫번째 식은 설명했지만, 두번째는 설명하지 못했다.

그 부분을 살펴보겠다.

 

j 가 item[i][0] 보다 작을 경우

=> dp[i][j] = dp[i-1][j]

 

dp[4][3]을 살펴보자

 

j는 무게로, 3이다.

i는 물건으로 4이다.

 

item[4][0] = 5 라서

j < item[4][0] 이다.

 

즉 가방에 3무게 만큼 물건을 넣을 수 있는데,

i번째 물건의 무게는 5로 더 크다.

그래서 i번째 물건은 넣을 수 없다. 고려할 사항이 아니게 된다.

 

때문에 i-1번째 dp값, 즉 0~3번째 물건 중 선택해서 무게 3을 만든 경우로

i번째 dp값을 채우면 되는 것이다.

=> dp[4][3] = dp[3][3]

 

 

 

3. 최종 코드

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 item[][] = new int[N+1][2];
		
		for(int i=1; i<=N;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			item[i][0] = Integer.parseInt(st.nextToken());
			item[i][1] = Integer.parseInt(st.nextToken());
		}
	
		
		int dp[][] = new int[N+1][K+1];
		
		
		for(int i = 1; i<=N; i++) {
			for(int j=1; j<=K; j++) {
				if(j>= item[i][0]) {
					
					dp[i][j] = Math.max(dp[i-1][j],  item[i][1] + dp[i-1][j-item[i][0]]);
					
				}else {
				
					dp[i][j] = dp[i-1][j];
			
				}
			}
		}
		
		
		System.out.println(dp[N][K]);
	}
	
}

 

참고 블로그 : 

https://dheldh77.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9CKnapsack-Problem

[알고리즘] 배낭 문제(Knapsack Problem)

https://fbtmdwhd33.tistory.com/60

[백준,BOJ 12865] 평범한 배낭(JAVA 구현, 추가풀이)