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

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

출력

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

---

문제 접근 방법

배낭문제는 knapsack 알고리즘 문제로 구글에 치면 자세하게 나온다.

이문제도 마찬가지로 knapsack 문제이고 접근 방법은 다음과 같다.

 

먼저 표를보자.

 

우리가 구하고자 하는 값은 가치 합의 최대를 찾는것이다. 즉, 두번째 표에서 4행 7열에 14라는 값을 찾으면 되는 것이다. 참고로 두번째 표에서 행은 물건번호, 열은 가방이 감당 가능한 무게를 나타낸다.

 

이문제를 풀기위해서 고려해야 할경우는 두가지다.

현재 내가 넣을 물건의 무게가 가방이 감당 가능한 무게냐

현재 내가 넣을 물건의 무게가 가방이 감당 못하는 무게냐

이렇게 두가지를 살펴보면 된다.

 

1. 감당 못하는 무게일때
   감당 못하는 무게일땐 간단하다.
   바로 전 물건이 현재 무게일때 최대로 넣었던 가치를 갖고 오면된다.
   즉, dp[i][w] = dp[i-1][w] 가 된다.
   
   
2. 감당 가능한 무게일때
   감당 가능한 무게라면 두가지중 하나를 비교해서 넣어 dp 배열에 넣어주면 된다.
   첫번째로 바로 전 물건이 현재 무게일때 최대로 넣었던 가치.
   두번째로 현재 물건의 가치 + 남은 여유공간에 최대로 넣을수 있는 가치.
   두가지중 더 큰값으로 넣어주면 최대값이 된다.
   즉, dp[i][w] = Math.max( dp[i-1][w], v[i]+dp[i-1][W-w[i]] ) 이 된다.
   W : 가방이 감당가능한 총무게
   w[i] : i번째 물건의 무게
   v[i] : i번째 물건의 가치

위에서 작성한 점화식을 이용해서 풀수있다.

또한 이문제가 왜 dp문제냐 라고 궁금해 한다면... 다른 포스팅에서도 설명했지만
1. 작은문제의 반복
2. 초기값이 일정

이 두가지를 확인해보면 되고 이문제는 두가지 조건을 모두 만족하는 문제이다. 따라서 dp문제라 할수 있다. 

 

복습하는 문제이기 때문에 간략하게 설명했고 자세한 내용은 https://record-developer.tistory.com/45 여기에 설명돼 있다.

---

풀이

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 [][] arr;// arr[물건번호][무게or가치]
	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 maxW = Integer.parseInt(st.nextToken());
		
		arr = new int[N+1][2];
		dp = new int[N+1][maxW+1];
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<2; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		/* 
		 *  if( 현재 물건 무게(arr[i][1]) <= 감당 가능 무게(W) )
		 *  dp[i][w] = Math.max( dp[i-1][W] , arr[i][0] + dp[i-1][W-arr[i][1] )
		 *
		 *	else if( 현재 물건 무게(arr[i][1]) > 감당 가능 무게(W) )
		 *	dp[i][w] = dp[i-1][W]
		 * 
		 */
		
		System.out.println(knapsack(N,maxW));
	}
	
	//TopDown
	public static int knapsack(int i, int w) {
		if(dp[i][w]==0 && w!=0 && i!=0) {//0행0열이 아닐때 dp값 계산 안됐으면 계산하기
			if(arr[i][0] <= w) {//현재물건무게 <= 감당 가능 무게
				dp[i][w] = Math.max( knapsack(i-1, w), arr[i][1] + knapsack(i-1, w-arr[i][0]) );
			}else {//현재물건무게 > 감당 가능 무게
				dp[i][w] = knapsack(i-1, w);
			}
		}
		return dp[i][w];
	}
}

 

BottomUp

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

public class Main {
	static int [][] dp;
	static int [][] arr;
	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 maxW = Integer.parseInt(st.nextToken());
		
		arr = new int[N+1][2];
		dp = new int[N+1][maxW+1];
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<2; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		/* 
		 *  if( 현재 물건 무게(arr[i][1]) <= 감당 가능 무게(W) )
		 *  dp[i][w] = Math.max( dp[i-1][W] , arr[i][0] + dp[i-1][W-arr[i][1] )
		 *
		 *	else if( 현재 물건 무게(arr[i][1]) > 감당 가능 무게(W) )
		 *	dp[i][w] = dp[i-1][W]
		 * 
		 */
		
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=maxW; j++) {
				if(arr[i][0] <= j) {
					dp[i][j] = Math.max( dp[i-1][j], arr[i][1]+dp[i-1][j-arr[i][0]]);
				}else {
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		
		System.out.println(dp[N][maxW]);
	}	
}

---

마치며

이번에는 전에 풀었던 것과 다르게 dp배열을 2차원배열로 했는데 메모리 측면에서 1차원배열이 더 효율적이지만 직관적으로 보기에는 2차원 배열이 더 낫다고 생각한다.