[백준 JAVA] 12865번: 평범한 배낭

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

 

대표적인 0/1 Knapsack 문제 dp를 이용하여 풀 수 있는 문제여서 다시 한번 정리하며 풀어보려한다.

 

참고로 물건의 쪼개서 넣을 수 있으면 Fraction Knapsack Problem이다. 이 문제는 Greedy한 방법으로 풀이 할 수 있다.

 

이문제에서 N< 100 이고, K < 100000 이므로 이중 for문을 이용하여 O(N * K)로 풀이 가능하다.

 

dp배열 생성 : dp[N][K] 는 배낭 무게제한이 K일때 N번째 물건까지 넣었을때의 최대 가치를 의미한다.

 

점화식 : N번째 물건의 무게는 W, 가치는 V라고 했을 때

 

배낭에 물건을 넣을 수 있으면

즉, K >= W 라면 dp[N][K] = MAX( dp[N - 1][K], dp[N - 1][K - W] + V) -> 이전물건까지 넣었을때의 최대값, 해당물건의 무게를 뺀  이전물건까지 넣었을때의 최대값 + 해당 물건 무게 중 큰값이다.

아니라면 dp[K][N] 은 dp[N - 1][K] -> 이전 물건을 넣었을때의 최대값이다.

 

예시를 통해 점검하자

 

K \ N	1	2	3	4
1	0	0	0	0
2	0	0	0	0
3	0	0	6	0
4	0	8	8	0
5	0	8	8	12
6	13	13	13	13
7	13	13	14	14

 

이런식으로 정답은 dp[N][K]  = 14가 된다.

 

풀이 코드

 

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

public class Main {
    public static int N, K;
    public static int[][] items, dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 1. 입력받기
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        items = new int[N + 1][2];
        dp = new int[N + 1][K + 1];
        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            items[i][0] = Integer.parseInt(st.nextToken());
            items[i][1] = Integer.parseInt(st.nextToken());
        }

        for(int n = 1; n <= N; n++){
            for(int k = 1; k <= K; k++){
                if(k >= items[n][0]) {
                    dp[n][k] = Math.max(dp[n-1][k], dp[n - 1][k - items[n][0]] + items[n][1]);
                } else {
                    dp[n][k] = dp[n-1][k];
                }
            }
        }

        System.out.println(dp[N][K]);
    }
}

 

0/1 배낭은 “역순 용량 루프”를 쓰면 1차원 배열로 동일 결과를 얻고 메모리는 O(K)로 감소하고 캐시 히트도 좋아져 보통 더 빠르다고 해서 다시 풀어보려고 한다.

 

단순하게 생각하자면 dp를 만들때 n 값은 이전값만 참고하므로 기존에 쓴 1차원 배열 하나만 필요하다.

 

또한 아이템을 저장할때 2차원으로 하는것이 아닌 1차원 배열 두개로 하면 좀 더 의미가 명확해져서 실수할 확률이 더 줄어든다한다.

 

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

public class Main {
    public static int N, K;
    public static int[] w, v, dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 1. 입력받기
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        w = new int[N + 1];
        v = new int[N + 1];
        dp = new int[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++) {
            int wi = w[i], vi = v[i];
            if (wi > K) continue;
            for (int k = K; k >= wi; k--) {
                int cand = dp[k - wi] + vi;
                if (cand > dp[k]) dp[k] = cand;
            }
        }

        System.out.println(dp[K]);
    }
}

 

 

포인트: 용량 k를 내림차순으로 순회해야 같은 아이템을 중복 사용하지 않는다.

 

dp 문제는 좀 더 풀어야 확실하게 감을 잡을꺼 같다. 이전보다는 그래도 많이 좋아졌다.