[JAVA] 백준 (골드5) 12865번 평범한 배낭

링크

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

---

입력 예제

4 7
6 13
4 8
3 6
5 12

---

출력 예제

14

---

풀이

이 문제는 배낭 문제(KnapSack Problem)로 짐을 쪼갤 수 있는 Fractional KnapSack Problem와 짐을 쪼갤 수 없는 0/1 KnapSack Problem 중에 후자에 해당한다. 전자는 Greedy, 후자는 DP로 풀 수 있다.

2차원 배열로 구성할 수도 있지만, 1차원 배열로 구성하여 중복 탐색을 피해가면 불필요한 탐색을 줄일 수 있다.

dp[i]: 무게 i일 때 최대 가치

모든 물건에 대해 탐색하면서, 버틸 수 있는 무게인 K부터 탐색하고 있는 현재 물건의 무게까지 역순으로 탐색을 한다.

for (int i = 0; i < N; i++) {  //모든 물건에 대해 탐색
	for (int j = K; j >= weights[i]; j--) {
		dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
	}
}

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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[] dp = new int[K + 1];  //dp[i]: 무게 i의 최대 가치
        int[] weights = new int[N + 1];
        int[] values = new int[N + 1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int W = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            weights[i] = W;
            values[i] = V;
        }

        for (int i = 0; i < N; i++) {
            for (int j = K; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }

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