[JAVA] BOJ(백준) - 평번한 배낭 - 12865번

문제내용

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

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

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

출력

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

 

---

문제 접근 방법

문제 개요부터 대표적인 '냅색' 문제라고 설명해주는데 냅색문제가 뭔지 몰라서 구글링해 보고 어떤 문제를 말하는지 알게돼서 그것을 기반으로 문제를 풀었다. 개인적으로 LCS와 비슷하다 생각했다ㅋㅋ.

 

먼저 냅색 문제는 2가지로 나뉘는데 무게를 쪼개서 넣을수 있는 경우와 무게를 쪼개지 못하는 경우로 나뉜다.

첫번째의 경우 그리디알고리즘으로 풀어야한다고 하지만

두번째의 경우 dp를 이용해 풀 수 있다는걸 알았다. 냅색에 대한 자세한 내용은 구글링해보길 바란다.(후에 포스팅 할 수 있으면 할생각!)

 

아무튼 문제의 알고리즘이 어떻게 이뤄지는지 알기 위해 표를 그려보는게 좋다. 

아래의 표를 보기전에 

물건의 무게와 가치를 items[][] 배열로 정의했고, 열의경우 무게와 가치로 나뉘고 행의 경우 몇번째 물건인지 알려주는 값이다.

그리고 dp배열의 경우 'dp[몇번째 물건인지][수용가능 무게] = 계산된 가치'로 정의했다.

 

첫번째 표는 입력받은 물건을 나타내고, 두번째 표는 문제에서 계산해야알 표이다.

두번째 표에서 행은 몇번째 물건인지, 열은 수용가능한 무게를 나타낸다.

 

1. 첫번째 물건이 들어왔을때(6, 13)

-> 첫번째 물건의 무게는 6이다. 때문에 (1,6)부터 물건을 가방에 넣을 수 있다.

 

2. 두번째 물건이 들어왔을때(4, 8)

-> 두번째 물건의 무게는 4이다. 때문에 (2,4)부터 물건을 가방에 넣을 수 있다.

하지만 (2,6)부터는 첫번째 물건도 들어올수 있다. 따라서 첫번째 물건을 넣을지 두번째 물건을 넣고 남은 무게에 알맞은 물건을 찾아 넣던지 해야한다. 이때 두번째 물건을 넣는다면 수용가능 무게는 2가되고 2의 무게를 갖고 있는 물건은 없다. 따라서 가치값이 최대가되는 첫번째 물건을 넣게된다.

단, 두가지 경우가 가능하다면 두가지 경우 중 최댓값을 넣어 주면된다.

 

3. 세번째 물건이 들어왔을때(3, 6)

-> 세번째 물건이 무게는 3이다. 때문에 (3,3)부터 물건을 가방에 넣을 수 있다.

그리고 (3,4) ,(3,5), (3,6), (3,7)은 2번과 마찬가지의 원리로 이전에 메모제이션 했던 값이나 세번째 물건을 넣고 다른 물건을 넣을수 있을때의 경우 두가지를 비교해 최댓값을 갱신해준다.

(3,6)의 경우를 보면 수용가능 무게가 6일때 최대값은 13이다. 그리고 세번째 물건의 무게가 3이라서 세번째 물건을 2개 넣을수 있다. 이땐 값이 12가된다. 따라서 13과 12를 비교하고 최댓값인 13을 넣게된다.

(3,7)의 경우를 보면 수용가능 무게가 7일때 최대값은 13이다. 그리고 세번째 물건의 무게가 3이라서 세번째 물건을 넣는다면 수용가능 무게가 4가남기 때문에 이전에 수용가능 무게가 4일때 최댓값을 계산했을때를 갖고와서 14가 된다.

따라서 최댓값은 14로 갱신된다.

 

4번물건이 들어왔을때도 위의 원리로 값이 입력된다.

이때 점화식을 살펴보면 물건의 인덱스를 i, 수용가능 무게를 j 라고한다면 2가지로 나눠서 생각할 수 있다.

 

1. j >= items[i][0] 일때 ( 수용가능 무게 >= 물건의 무게)

-> 최대 가치값 = max(현재 물건가치+이전에 탐색했던 값중 현재 물건의 무게를 뺀 무게를 갖고있는 최대값, 이전에 탐색했던 값중 수용가능 무게내에서 담을수 있는 물건의 무게중 최대 가치값)

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

2. j < items[i][0] 일떄 ( 수용가능 무게 < 물건의 무게)

-> 최대 가치값  = 이전에 탐색했던 값중 수용가능 무게내에서 담을수 있는 물건의 무게중 최대 가치값

즉, dp[i][j] = dp[i-1][j]

 

위의 점화식을 따르는 알고리즘 이란것을 알 수 있다.

그럼 위의 점화식을 이용해 문제를 구현해내기만 하면된다.

 

그리고 ButtomUp의 경우 dp를 1차원 배열로도 푼 분들이 있어서 해당 코드도 갖고와봤다.

 

---

풀이

TopDown

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[][] dp; //dp[몇번째 물건][수용가능 무게] = 계산된 가치
	static int[][] items; //행:몇번째 물건, 1열:무게, 2열:가치
	
	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());
		
		//0행 0열은 0으로 초기화.
		items = new int[N+1][N+1];
		dp = new int[N+1][K+1]; 
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<2; j++) {
				items[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int max = Integer.MIN_VALUE; 
		//1~N물건까지 넣어보면서 K무게 내에서 가치가 최대가되는 값 찾기. 
		for(int i=1; i<=N; i++) {
			max = Math.max(max, knapsack(i,K));
		}
		
		System.out.println(max);
	}
	
	public static int knapsack(int i, int j) {
		//물건의 가치나 무게가 1보다 작아지면 0반환
		if(i<=0 || j<=0) {
			return 0;
		}
		//계산안된 값들 계산
		if(dp[i][j]==0) {
			//수용가능 무게보다 물건의 무게가 클때와 작거나 같을때로 나눔.
			if(j < items[i][0]) {
				//이전물건을 탐색하면서 물건의 무게가 수용가능 무게보다 
				//작거나 같은것들을 찾음. 
				dp[i][j] = knapsack(i-1,j);
			} else if(j >= items[i][0]) {
				//이전에 탐색한 물건의 가치값에 현재 물건을 가방에 추가로 넣은 값과
				//이전에 탐색한 물건의 가치값을 비교해서 최댓값을 갱신.
				dp[i][j] = Math.max(knapsack(i-1, j-items[i][0]) + items[i][1], knapsack(i-1, j));
			}
		}
		return dp[i][j];
	}
}

 

BottomUp

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[] dp; //dp[수용가능 무게] = 계산된 가치값
	static int[][] items;
	
	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());
		
		items = new int[N+1][N+1];
		dp = new int[K+1]; 
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<2; j++) {
				items[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=1; i<=N; i++) {
			//수용가능한 무게의 최대부터 시작해서 i번째 물건이 드갈수 있는 위치를 한정시켜주고
			//dp값+물건가치와 dp값을 비교해 최댓값 갱신.
			//이렇게하면 전부 탐색이아니라 불필요한 탐색은 안하게됨.
			for(int j=K; j-items[i][0]>=0; j--) {
				dp[j] = Math.max(dp[j-items[i][0]]+items[i][1], dp[j]);
			}
		}
		
		System.out.println(dp[K]);
	}
}

 

---

마치며

이번엔 냅색이라는 알고리즘에 대해 공부해볼 수 있는 문제였다. 그리고 풀이와 효율을 따지면 확실히 BottomUp방식이 더 좋게 나온다. 저런 방법은 어떻게 생각해내는건지... 참..

꾸준히하면 언젠가 가능하다고 생각하긴한다. 화이팅하자ㅎㅎ