백준 12865 평범한 배낭 - JAVA

문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

<Top - down>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N;
    static int K;
    static Integer[][] dp;
    static int w[];
    static int v[];
    
    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());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        dp = new Integer[N][K+1];
        w = new int[N];
        v = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st.nextToken());
        } 
        bw.write(String.valueOf(knapsack(N-1, K)));
        bw.flush();
    }
    
    private static int knapsack(int i, int k) {
        if (i < 0) {
            return 0;
        } 
        if (dp[i][k] == null) {
            if(w[i] > k) {
                dp[i][k] = knapsack(i-1, k);
            } else {
                dp[i][k] = Math.max(knapsack(i-1, k), knapsack(i-1, k - w[i]) + v[i]);
            }
        }
        return dp[i][k];
    }
}

 

<Bottom - up>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N;
    static int K;
    static int[][] dp;
    static int w[];
    static int v[];
    
    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());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        dp = new int[N+1][K+1];
        w = new int[N+1];
        v = new int[N+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());
        } 
        knapsack();
        bw.write(String.valueOf(dp[N][K]));
        bw.flush();
    }
    
    private static void knapsack() {
        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]);
                }
            } 
        } 
    }
}

 

Knapsack problem

---

냅색문제는 유명한 동적계획법 문제입니다. 해당 문제에 주어진 아이템들의 무게, 가치를 고려하여 배낭에 넣을 수 있는 조건을 만족하는 최대 무게를 찾는 문제입니다. 냅색문제는 아이템의 무게를 쪼갤 수 있는 '분할 가능한 배낭 문제(fractional knapsack problem)'와 아이템의 무게를 쪼갤 수 없는 '0-1 배낭 문제(0-1 Knapsack Problem)'로 나누어 집니다. fractional knapsack 문제는 그리디 알고리즘으로 해결가능하고, 0-1 knapsack 문제는 동적 계획 법으로 풀이가 가능합니다.

- 나무위키<배낭문제> 참고 -

 

0-1 배낭 알고리즘은 이 글을 적고 있는 저도 이해를 하는데 오랜 시간이 걸렸지만, 해답을 있는 그대로 받아들이면서 익숙해지는 것이 냅색 알고리즘을 빠르게 풀 수 있는 방법이라고 생각합니다... 이유는 동적 계획법 문제이기 때문에 점화식이 존재하기 때문입니다.개인적으로 점화식을 설명드리는 것 보다는 dp표를 만들어 설명드리는 것이 이해하기 쉽다고 생각하기 때문에 표로 설명드리겠습니다.

 

배낭에 들어갈 수 있는 아이템의 개수를 N, 배낭의 최대무게를 K라고 할때, 먼저 선언해야할 dp배열은 아래와 같습니다.

---

각 셀에는 해당 무게까지 각 아이템을 사용해서 담을 수 있는 최대 가치를 넣습니다.

---

해당문제의 예제를 기준으로 1번 아이템부터 천천히 보여드리겠습니다. 1번 아이템만 사용하는 경우에는 아래와 같습니다.

1번 아이템까지 사용하는 경우 1번 아이템의 무게가 6kg이기 때문에 5kg까지는 아무것도 들어갈 수 없고, 6kg이상부터 1번 아이템의 가치인 13의 가치가 들어갈 수 있습니다.

---

2번 아이템까지 사용하는 경우에는 아래와 같습니다.

2번 아이템까지 사용하는 경우도 동일합니다. 단지, 4kg와 5kg의 경우 2번 아이템의 무게만 들어갈 수 있기 때문에 2번 아이템까지 사용 할 수 있는 경우의 최대 가치는 8입니다.

---

3번은 아이템까지 사용하는 경우에는 아래와 같습니다.

3번의 경우에는 3kg인경우 3번 아이템만 들어갈 수 있기때문에 6의 가치를 넣어줍니다. 마지막 7kg의 경우에는 1번 아이템을 넣어서 13의 가치를 얻는것 보다, 3번 아이템을 넣고 6의 가치를 얻은 후, 3번 아이템을 제외한 가치중에서 남은 무게4kg(7-3)에 매핑될 수 있는 최대값인 8의 가치를 더해 총 14의 가치를 얻는 것이 더 큰 가치이기 때문에 14의 가치를 매핑합니다. 핵심은 dp배열에서 어떤 위치의 값을 가져오는지 잘 살펴보는 것입니다.

---

4번 아이템까지 사용하는 경우에는 아래와 같습니다.

4번의 경우에도 결과 도출하는 과정은 동일합니다. 5kg의 경우 4번 아이템을 넣는 것이 최대의 가치이기 때문에 12를 매핑해줍니다. 마지막 7kg의 경우 4번 아이템을 사용해서 12의 가치와 남은 무게 2kg(7-5)에 매핑될 수 있는 최대값인 0의 가치를 더해 총 12의 가치를 얻는 것보다 2번과 3번 아이템의 가치를 더한 14의 값이 더 큰 가치이기 때문에 14의 가치를 매핑합니다.

---

눈치채신 분들도 계시겠지만 dp배열 매핑과정의 핵심은 사용가능한 최대 무게에서 신규로 사용가능한 아이템의 무게를 빼는 것입니다.

3번 아이템이 추가된 경우에는 7kg - 3kg가 되어 배낭에 담긴 4kg의 가치와, 3번 아이템의 가치를 더해 이전 2번 아이템이 신규로 추가된 경우의 7kg의 가치와 비교하고, 4번 아이템이 추가된 경우에는 7kg - 5kg가 되어 배낭에 담긴 2kg의 가치와, 4번 아이템의 가치를 더해 이전 3번 아이템이 신규로 추가된 경우의 7kg의 가치와 비교하는 것입니다.

 

알고리즘 설명

---

 

기본적으로 바텀업(반복)과 탑다운(재귀) 2가지 방식으로 모두 풀이 가능합니다. 또 dp배열을 1차원으로 선언해 무게별 최대 가치만을 매핑하여 해결할 수 도 있지만 해당 설명에서는 고려하지 않았습니다.

1번 아이템을 제외하고 N번 아이템까지 사용하여 최대 가치의 배낭을 채우는 경우에는 먼저 N-1번 아이템까지 사용하는 경우의 수를 받아옵니다.

신규 아이템을 i, 배낭에 담을 수 있는 무게를 j라고 했을때, dp[i-1][j]값과 dp[i-1][j-해당아이템의 무게] + 해당 아이템의 가치의 값을 비교하여 메모이제이션을 활용해 푸는 문제입니다. 점화식을 수식으로 알지 못해도, dp배열에 매핑할 값을 구하는 과정을 알게 된다면 응용문제도 어렵지 않게 풀 수 있을것이라고 생각합니다.

 

코드 해석

---

바텀업 방식은 단순 반복문으로 점화식만 알고있다면 위의 설명으로 충분하기 때문에 탑다운 방식으로 설명드리겠습니다. 아이템의 개수(N)과 배낭 최대 무게(K)를 입력, N만큼 각 아이템의 무게(w)와 가치(v)입력받고, dp 2차원 배열을 선언하고 초기화합니다. N-1인 마지막 아이템부터 시작하여 배낭 K의 용량에서 최대가치를 계산합니다. 첫 번째 아이템인 경우에는 i < 0이면 그 전의 아이템은 없으므로 0을 리턴합니다. dp[i][k]가 null인 경우에 dp배열을 매핑하는데, 배낭에 담을 수 있는 무게보다 현재 아이템의 무게가 더 크다면 이전 아이템까지의 최대가치를 매핑하고, 현재 아이템의 무게가 배낭에 담을 수 있는 무게보다 작다면, 현재 아이템이 제외된 knapsack(i-1, k)와 현재 아이템이 제외된 knapsack(i-1, k - w[i]) + v[i] 중에 더 큰 값을 선택해 dp[i][k]에 매핑합니다.