Baekjoon 12865 평범한 배낭 JAVA

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)가 주어진다.

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

출력

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

풀이

다이나믹 프로그래밍을 이용하여 푸는 배낭 문제이다.

W는 무게, 가치는 V이다.

4 7
6 13
4 8
3 6
5 12

입력받는 예제이다. 최대 물품의 개수를 4개, 최대로 넣을 수 있는 무게는 7이다.

여기서 정답은 4kg 8, 3kg 6 물건을 넣는것이 14로 최대 가치로 가질 수 있는 값이다.

 

먼저 배열을 만들어서 1 2 3 4 5 6 7 무게별로 들 수 있는 물건들을 정리한다.

1. 6kg 13

1	2	3	4	5	6	7
-	-	-	-	-	13	13

배열이 생성이 된다.

 

2. 4kg 8

1	2	3	4	5	6	7
-	-	-	8	8	13	13

위의 배열은 7kg에서 4kg를 빼면 3에 넣을 수 있는데, 3kg는 4kg의 물건을 넣을 수 없기에 넘어가게 된다.

그래서 4와 5에만 8의 가치를 넣을 수 있다.

 

3. 3kg 6

1	2	3	4	5	6	7
-	-	6	8	8	13	14

위의 배열은 7kg에서 4kg를 빼면 3에 넣을 수 있는데, 3kg는 4kg의 물건을 넣을 수 없기에 넘어가게 된다.

그래서 4와 5에만 8의 가치를 넣을 수 있다.7부터 시작해서 3까지 탐색을 하게 된다.

7kg에서 이번에 넣을 무게 3kg를 뺀 4kg의 가치는 8이고 여기에 6의 가치를 넣으면 14로 7kg에서 들 수 있는 무게가 업데이트 된다.

 

 

4. 5kg 12

1	2	3	4	5	6	7
-	-	6	8	12	13	14

7부터 시작해서 5까지 탐색을 하게 된다.

7kg에서 이번에 넣을 무게 5kg를 뺀 2kg의 가치는 0이고 여기에 12의 가치를 넣으면 12로 7kg에서 들 수 있는 가치가 계산되지만 이미 존재하는 14보다 작은 가치이기에 넘어간다.

6kg도 동일하게 13이 더 높은 가치이기 때문에 넘어간다.

5kg일때는 8의 가치이고 0kg + 5kg의 가치는 12이기에 5kg에서 들 수 있는 가치는 12로 업데이트 된다.

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken()), k=Integer.parseInt(st.nextToken());
		int [] w=new int[n], v=new int[n], dp = new int[k+1];
		for(int i=0;i<n;i++) {
			st=new StringTokenizer(br.readLine());
			w[i]=Integer.parseInt(st.nextToken());
			v[i]=Integer.parseInt(st.nextToken());
		}
		for(int i=0;i<n;i++) {
			for(int j=k;j>=w[i];j--) {
				dp[j]=Math.max(dp[j], dp[j-w[i]]+v[i]);
			}
		}
		System.out.println(dp[k]);
	}
}