[BOJ/Java] 12865. 평범한 배낭

[BOJ/Java] 12865. 평범한 배낭

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

---

문제 해석

평범한 배낭 문제는 주어진 물건들의 무게와 가치를 고려하여 배낭의 최대 용량 내에서 가치의 합이 최대가 되도록 물건을 선택하는 문제이다. 이 문제는 전형적인 **배낭 문제(Knapsack Problem)**로, 동적 프로그래밍을 활용하여 해결할 수 있다.

풀이 과정

1. 초기 설정: 물건의 개수(N)와 배낭의 최대 용량(K)을 입력받는다. 각 물건의 무게와 가치를 저장할 배열을 선언한다.
2. 동적 프로그래밍 테이블 구성: `dp[i][j]`는 배낭의 용량이 `j`일 때, 처음 `i`개의 물건 중에서 선택한 최대 가치를 의미한다. 이 테이블을 초기화한다.
3. 점화식 적용: 각 물건에 대해 배낭의 용량을 1부터 K까지 순회하며, 현재 물건을 배낭에 넣을지 말지 결정한다. 점화식은 다음과 같다:
   • 현재 물건의 무게가 배낭의 용량보다 크면: `dp[i][j] = dp[i-1][j]`
   • 현재 물건의 무게가 배낭의 용량보다 작거나 같으면: `dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])`
4. 결과 출력: `dp[N][K]`는 배낭의 용량이 K일 때, N개의 물건 중에서 선택한 최대 가치를 의미한다. 이를 출력한다.

코드

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

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[] weights = new int[N + 1]; // 물건의 무게
        int[] values = new int[N + 1]; // 물건의 가치

        // 물건의 무게와 가치 입력
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            weights[i] = Integer.parseInt(st.nextToken());
            values[i] = Integer.parseInt(st.nextToken());
        }

        // DP 테이블 초기화
        int[][] dp = new int[N + 1][K + 1];

        // DP 테이블 채우기
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                if (weights[i] > j) {
                    // 현재 물건을 배낭에 넣을 수 없는 경우
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 현재 물건을 배낭에 넣을 수 있는 경우
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
                }
            }
        }

        // 결과 출력
        System.out.println(dp[N][K]);
    }
}

시간 복잡도 분석

시간 복잡도는 O(N * K)이다. 물건의 개수(N)와 배낭의 용량(K)에 대해 이중 반복문을 사용하여 DP 테이블을 채우기 때문이다. 이는 문제의 제약 조건 내에서 효율적으로 동작한다.

느낀점

이 문제는 전형적인 배낭 문제로, 동적 프로그래밍의 기본적인 개념을 이해하는 데 매우 유용하다. 점화식을 통해 문제를 해결하는 과정에서 동적 프로그래밍의 강력함을 느낄 수 있었다. 특히, 물건을 선택하거나 선택하지 않는 두 가지 경우를 고려하여 최적의 해를 구하는 방식이 인상적이었다. 이러한 문제는 실생활에서도 자원 할당이나 최적화 문제에 적용될 수 있을 것 같다.