[백준]12865번 : 평범한 배낭 - 자바(JAVA)

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

12865번: 평범한 배낭

 

문제 해석

필요한 물건의 개수 : N개

각 물건의 무게 : W

각 물건의 가치 : V

 

배낭에 물건을 넣고자하는데 최대 K만큼의 무게를 넣을 수 있다.

이 때 물건의 가치가 최대가 되도록 물건을 넣어보자.

---

문제 풀이 전 설계

입력값 받기

물품의 개수 N과 최대 무게 K를 입력받고 N번에 걸쳐 물건의 무게(W)와 물건의 가치(V)를 입력받는다.

 

핵심 기능

배낭에 물건을 어떻게 최대가치로 넣을것인가.

N이 0~100사이이기 때문에 완전탐색인 조합으로 문제를 풀기에는 무리가 있어 보입니다.

DP 배열을 선언하여 해당무게까지 최대로 넣을 수 있는 가치를 저장하여 활용합니다.

 

자료구조

물건의 무게와 가치를 컬렉션 자료구조 Map에 저장하면 좋을 것 같다.

하지만 물건의 무게가 중복될 수 있기 때문에 List<K,V> 를 사용하거나 item 객체를 만들어서 List<Item> 등으로 활용해야 할 것 같습니다.

 

---

풀이하면서 고민해본점

예를들어 K = 7, N=6일때

1 1

1 3 

1 5

1 6

2 5

3 1

DP[1] 에는 무게가1일때 최대가 담겨있음 DP[1] = 6

DP[2]를 구할때는 DP[1] + 또다른 1을 최대값을 구해야 함  또는 Weight이 2일인 물품의 가치의 최대 = 11 vs 4

DP[3] = DP[2] + DP[1] 이 불가능함 그러면 가치가 5인 item을 2개 활용하는것이니..

 

즉, DP 배열을 활용하기 위해서는 계속 이전 DP배열들의 값이 바뀌어야함

만약에 DP[1] = 5을 사용했는데 DP[2] = 5 + 4 를 사용했다면 이제 DP[1] = 3

그래서 DP[3] = 12 와 1을 비교해서 큰값넣기

 

따라서 2차원 DP를 활용해야 합니다.

1번 item만 넣었을 경우, 2번 item까지 넣었을 경우, 3번 item 까지 넣었을 경우 ~ N번 item까지 넣은 경우를 하나의 차원으로 사용합니다.

다른 하나의 차원은 무게가0일때, 1일때, 2일때 ~ k일때까지를 사용합니다.

 

DP[y번 item까지 넣은 경우][x 무게일때]

0 <= y <= N

0 <= x <= k

 

N=6 , K = 7

1번 item은 (1,2)

2번 item은 (1,1)

3번 item은 (1,5)

4번 item은 (2,3)

5번 item은 (3,1)

6번 item은 (4,4)

라고 가정해보겠습니다.

 

알고리즘은 다음과 같습니다.

for(int i=1;i<=N;i++) {
	for(int j=1;j<=K;j++) {
		DP[i][j] = DP[i-1][j]; // 기본적으로 이전 아이템의 가치를 저장한다.
		Item tempItem = bagList.get(i-1);
		if(j - tempItem.weight >=0) { // 무게에서 자신의 무게를 뺐을 때 남는 무게가 존재하면
			DP[i][j] = Math.max(DP[i-1][j], DP[i-1][j-tempItem.weight]+tempItem.value); 
			// 이전 아이템에서 구한 가치와 남은 무게의 가치 + 자신의 가치 중 큰 값을 취한다.
		}
	}
}

 

1. 이전값을 그대로 DP[i][k]에 넣어줍니다.

2. i번째 물건의 정보를 받아옵니다.

3. 만약 i번째 물건의 무게가 k보다 크다면 이전값을 넣어준채로 끝나게 됩니다.

4. 그렇지 않다면 이전값과, k-weight번째를 비교해 큰값을 넣어줍니다.

 

 

이것을 표로 나타내 보겠습니다.

 

1번 item은 weight 1, value 2입니다.

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	2	2	2	2	2	2	2
2번 item
3번 item
4번 item
5번 item
6번 item

1번 item의 이전값은 DP[0][1] ~ DP[0][K]이기 때문에 모두 0입니다.

또한 무게가 1이기 때문에 모든 무게에 들어갈 수 있습니다.

Math.max(이전값 , 현재가치(2) + DP[0][K-무게]) 에서 [K-무게]에 어떤값이 들어가던 0이기 때문에 모두 2라는 값이 들어가게 됩니다.

 

2번 item은 weight 1, value는 1입니다.

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	2	2	2	2	2	2	2
2번 item	2	3	3	3	3	3	3
3번 item
4번 item
5번 item
6번 item

2번 item의 이전값은 모두 DP[1][1] ~ DP[1][K]이기 때문에 모두 2입니다.

또한 무게가 1이기 때문에 모든 무게에 들어갈 수 있습니다.

Math.max(이전값, 현재 가치(1) + DP[1][K-무게]에 어떤값이 들어가던 3이기 때문에 모두 3이라는 값이 들어가게 됩니다.

단 DP[2][1] = Math.max( 이전가치(2),  현재 가치(1) + DP[1][j (1) - tempItem.weight(1)])입니다.

이때는 j - tempItem.weight = 0이므로 0이 들어가게 되고 2값이 들어가게 됩니다.

 

3번 item은 weight 1, value는 5입니다.

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	2	2	2	2	2	2	2
2번 item	2	3	3	3	3	3	3
3번 item	5	7	8	8	8	8	8
4번 item
5번 item
6번 item

3번 item의 무게는 1이여서 처음부터 담을 수 있습니다.

무게 1에는 이전값보다 5가 더 크기때문에 5로 채워집니다.

무게 2에는  현재가치 (5) + 이전가치(2)이  > 3 이기 때문에 7으로 채워집니다.

무게 3에는 현재가치(5) + 이전가치(3) > 3  이기 때문에 8으로 채워집니다.

- >반복

 

4번 item은 weight 2, value는 3입니다.

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	2	2	2	2	2	2	2
2번 item	2	3	3	3	3	3	3
3번 item	5	7	8	8	8	8	8
4번 item	5	7	8	10	11	11	11
5번 item
6번 item

4번 item의 무게는 2여서 처음부터 담을 순 없습니다.

따라서 무게1에는 이전값인 5가 오게 됩니다.

 

무게2에는 현재 가치(3) + DP[3][0]=0 < 7이기 때문에 7으로 채워집니다.  

무게3에는 현재 가치(3) + DP[3][1]=5 = 8이기 때문에 8으로 채워집니다.

무게4에는 현재 가치(3) + DP[3][2]=7 > 8이기 때문에 10으로 채워집니다.

무게5에는 현재 가치(3) + DP[3][3]=8 > 8이기 때문에 11으로 채워집니다.

-> 반복

 

5번 item은 weight 3, value는 1입니다.

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	2	2	2	2	2	2	2
2번 item	2	3	3	3	3	3	3
3번 item	5	7	8	8	8	8	8
4번 item	5	7	8	10	11	11	11
5번 item	5	7	8	10	11	11	11
6번 item

5번 item의 무게는 3이여서 처음부터 담을 순 없습니다.

따라서 무게1,2에는 이전값들이 채워집니다.

 

무게3에는 현재 가치(1) + DP[4][0] = 0 < 8 이기 때문에 8으로 채워집니다.

무게4에는 현재 가치(1) + DP[4][1] = 5 < 10 이기 때문에 10으로 채워집니다.

-> 반복

 

 

6번 item은 weight 4, value는 4입니다.

0번 item	무게 1	무게 2	무게 3	무게 4	무게 5	무게 6	무게 7
1번 item	2	2	2	2	2	2	2
2번 item	2	3	3	3	3	3	3
3번 item	5	7	8	8	8	8	8
4번 item	5	7	8	10	11	11	11
5번 item	5	7	8	10	11	11	11
6번 item	5	7	8	10	11	12	12

6번 item의 무게는 4이여서 처음부터 담을 순 없습니다.

따라서 무게1,2,3에는 이전값들이 채워집니다.

 

무게4에는 현재 가치(4) + DP[5][0] = 0 < 10 이기 때문에 10으로 채워집니다.

무게5에는 현재 가치(4) + DP[4][1] = 5 < 11 이기 때문에 11으로 채워집니다.

무게6에는 현재 가치(4) + DP[4][2] = 7 = 11 이기 때문에 11으로 채워집니다.

무게7에는 현재 가치(4) + DP[4][3] = 8 > 12 이기 때문에 12로 채워집니다.

 

이렇게 모든 테이블이 채워지게되며 DP[item개수][무게] = 12 가 정답이 됩니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

public class Main_12865_평범한배낭 {

	static class Item implements Comparable<Item>{
		int weight;
		int value;

		public Item(int weight, int value) {
			super();
			this.weight = weight;
			this.value = value;
		}

		@Override
		public String toString() {
			return "Item [weight=" + weight + ", value=" + value + "]";
		}

		@Override
		public int compareTo(Item o) {
			if(o.weight == this.weight) {
				return o.value - this.value;
			} 
			return this.weight - o.weight;
		}

	}

	static int N, K;	// N = 물품의 수, K = 버틸 수 있는 무게
	static int[][] DP;
	static List<Item> bagList = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		DP = new int[N+1][K+1];
		bagList = new ArrayList<Item>();
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int weight = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			
			bagList.add(new Item(weight,value));			
		}
									
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=K;j++) {
				
				DP[i][j] = DP[i-1][j]; // 기본적으로 이전 아이템의 가치를 저장한다.				
				Item tempItem = bagList.get(i-1);
				
				if(j - tempItem.weight >=0) { // 무게에서 자신의 무게를 뺐을 때 남는 무게가 존재하면,
					DP[i][j] = Math.max(DP[i-1][j], DP[i-1][j-tempItem.weight]+tempItem.value);
					// 이전 아이템에서 구한 가치와 남은 무게의 가치 + 자신의 가치 중 큰 값을 취한다.
				}
				
			}
		}
		System.out.println(DP[N][K]);
	}

}

 

출처

https://fbtmdwhd33.tistory.com/60

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