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

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

---

테스트 케이스

 

입력 1

4 6
6 13
3 8
7 15
2 6

출력 1

14

 

입력 2

4 7
6 13
4 8
3 6
5 12

출력 2

14

 

 

---

접근

대표적인 냅색 문제인듯 합니다.

핵심은 dp적으로 접근하는 것 입니다.

4 6
6 13
3 8
7 15
2 6

이런 테스트 케이스를 예로 들겠습니다.

가치	-> 배낭 공간 ↓배낭무게	1	2	3	4	5	6
13	6	0	0	0	0	0	13
8	3
15	7
6	2

첫째 줄 에서, 배낭 무게가 6이 될때까지 아무것도 못 넣으므로 0으로 일관되다가, 6일때 첫번째 물건을 넣어서 13이됩니다.

 

 

가치	-> 배낭 공간 ↓배낭무게	0	1	2	3	4	5	6
0	0	0	0	0	0	0	0	0
13	6	0	0	0	0	0	0	13
8	3	0	0	0	8
15	7	0
6	2	0

두번째 물건은 무게가 3이므로 배낭공간이 3일때 부터, 넣을 수 있습니다. 그러나 그냥 넣는 것이 아니고, 이전값과 비교해서 넣어야하는데,

해당칸의 바로위의 값 vs (해당 칸의 바로 위의 값에서 현재 넣으려는 물건의 사이즈를 뺀만큼의 결과값 + 현재 물건의 값)

을 비교하여 넣어야합니다.

위의 경우에는 바로 위의 값인 0과, 바로위의값의 공간 에서 현재 물건의 무게를 뺀(3-0 = 0) 결과값(0) 에다가 현재물건의 값(8)을 더해서 비교하여 8이 더크므로 8이 올라오게 됩니다.

 

 

 

가치	-> 배낭 공간 ↓배낭무게	1	2	3	4	5	6
13	6	0	0	0	0	0	13
8	3	0	0	8	8	8	13
15	7
6	2

그리고 위의 값이 계속 0이므로, 5번째 공간까지는 8로 지정되다가, 6번째에서는 위의값 13이 8보다 크기때문에 13이 옵니다.

 

 

 

이런식으로 모든 테이블을 채워가며 max값을 찾으니 해결되었습니다.

가치	-> 배낭 공간 ↓배낭무게	1	2	3	4	5	6
13	6	0	0	0	0	0	13
8	3	0	0	8	8	8	13
15	7	0	0	8	8	8	13
6	2	0	0	8	8	14	14

따라서 결과 값은  최댓값인 14

---

코드

	import java.util.*;
import java.util.stream.IntStream;
import java.io.*;
	
	class Main {
		
		public static void main(String args[]) throws IOException {
	    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    	StringTokenizer st =new StringTokenizer(br.readLine());
	    	int N = Integer.parseInt(st.nextToken());
	    	int K = Integer.parseInt(st.nextToken());
	    	int arr[][] = new int[N+1][K+1];
	    	int weightAndValue[][] = new int[N+1][2];
	    	int result = 0;
	    	for(int i=1; i<=N; i++) {
	    		st = new StringTokenizer(br.readLine());
	    		//weight
	    		weightAndValue[i][0] = Integer.parseInt(st.nextToken());
	    		//value
	    		weightAndValue[i][1] = Integer.parseInt(st.nextToken());
	    	}
	    	for(int i=1; i<=N; i++) {
	    		for(int j=1; j<=K; j++) {
	    			//현재 물건을 넣을 공간이 생길때까지 이전의 물건 결과 사용함.
	    			arr[i][j] = arr[i-1][j];
	    			if(j >= weightAndValue[i][0]) {
	    				//이전 결과 vs (이전결과에서 현재의 무게 결과를 뺸 결과 + 현재 물건 가치)
	    				arr[i][j] = Math.max(arr[i-1][j], arr[i-1][j-weightAndValue[i][0]] + weightAndValue[i][1]);
	    			}
	    			result = Math.max(arr[i][j], result);
	    			
	    		}
	    	}
	    	bw.write(String.valueOf(result));
	    	br.close();
	    	bw.flush();
	    	bw.close();
	    }
	}

---

주의

한 물건은 한번만 사용가능 합니다.

하나의 물건 두번 넣기 불가.