[BOJ/JAVA] 백준 12865번 평범한 배낭 ( DP )

 

✔ 문제

난이도 : 골드5 🥇

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

12865번: 평범한 배낭

 

N개의 물건이 주어질때 각 물건은 무게 W와 가치V를 가지는데, 해당 물건을 배낭에 넣어서 가면 V만큼 즐길 수 있습니다.

하지만 K만큼의 무게만 넣을 수 있는 배낭만 들고 다닐 수 있습니다.

이때 최대한 즐거운(가치가 높은) 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제입니다.

 

 

✔ 문제 풀이

 

대표적인 DP문제 중 하나인 "배낭(knapsack) 문제" 입니다.

배낭 문제는 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우로 나눌 수 있는데, 위의 문제는 짐을 쪼갤 수 없는 배낭 문제인 0/1 Knapsack Problem  이라고 합니다.

0/1 Knapsack Problem 문제는 DP 방법을 사용하여 풀어 낼수 있고 0/1이라고 붙여진 것은 각 아이템이 단 한번만 선택할 수 있기 때문입니다.

 

dp의 핵심은 메모이제이션을 통해 중복연산을 제거하는 것입니다.

그러기 위해서 무게(w)가 1에서부터 k까지 일때의 가치(v)를 dp배열에 기록하면서 기록된 값들을 통해 중복 연산을 하지 않고 문제를 풀 수 있습니다.

 

가장 직관적으로 1에서부터 k까지 배열을 채워나가는 bottom-up 방식이 가장 이해하기 쉬웠습니다.

for( int i = 1; i<=n; i++){
    for( int j = 1; j<=k; j++) {

        if( w[i] > j){
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
        }
    }
}

 

먼저 코드를 보겠습니다. 

탐색하려는 물건의 무게(w[i])가  메모이제이션 할 무게(j) 보다 크다면 이 물건은 기록될 수 없기 때문에 이전값(dp[i-1][j])을 입력합니다.

만약 i가 1이고 j가 1이라면 1이라는 무게를 충족하는 물건이 없기 때문에 dp[1][1] = dp[1-1][1]이 채워지게 되고 해당하는 값이 없다면 아래 그림처럼 계속해서 0으로 채워지게 됩니다.

 

하지만 메모이제션 할 무게(j)를 계속 늘리면서 해당하는 무게의 물건을 찾게되면 즉, 물건의 무게가  j보다 작거나 같다면 

 

dp[i][j] = Math.max(dp[i -1][j], dp[i-1][j - w[i]] + v[i]);

 

같은 무게를 만족하는 다른 물건의 가치와 ( dp[i-1][j] ),

지금 탐색중인 물건의 무게를 뺀 무게에 해당하는 물건과 탐색중인 물건의 가치를 더한 값 ( dp[i-1][j - w[i]] + v[i] )

중 더 큰 값을 해당 배열에 저장합니다.

 

 

위 그림에서 색칠한 부분을 보면 탐색중인 물건의 무게는 3이고 메모이제이션 하기위한 무게는 7입니다.

이전 물건(2)에 누적된 가치는 13입니다 이때, 탐색중인 물건(3)에 해당하는 무게는 3이기 때문에

j - w[i] 즉, 7에서 3을 뺀 무게인 4의 무게를 갖고있는 물건을 하나 더 배낭에 넣을 수 있습니다.

 

탐색하려는 물건의 가치와 4의 무게를 갖을 수 있는 물건의 누적된 최대 가치를 더하게 되므로써 최대의 조합을 얻을 수 있습니다.

 

🔎 전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
	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());
        int[] w = new int[n + 1];
        int[] v = new int[n + 1];
        int[][] dp = new int[n+1][k+1];

        for( int i = 1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st.nextToken());
        }

        for( int i = 1; i<=n; i++){
            for( int j = 1; j<=k; j++) {

                if( w[i] > j){
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                }
            }
        }
		System.out.println(dp[n][k]);
	}
}

 

 

---

 

📚 Reference : https://st-lab.tistory.com/141