[백준] 12865 : 평범한 배낭 - Java

백준 문제 URL

---

문제 요약

각 물건에는 무게(W)와 가치(V)가 주어진다.
배낭에는 최대 K 무게까지 물건을 넣을 수 있는데,
이때 얻을 수 있는 가치의 최댓값을 구하는 문제다.

단, 각 물건은 한 번만 넣을 수 있다.
즉, 0-1 배낭 문제(0-1 Knapsack Problem)을 그대로 구현해야 한다.

---

핵심 아이디어

이 문제는 조합적으로 보면 모든 경우의 수를 탐색(DP 없이) 해야 하므로
DFS나 완전 탐색으로 풀면 (O(2^n)) 시간 복잡도가 되어 터진다.

그래서 다음과 같은 DP 접근을 사용한다:

• dp[i]: “무게 i까지 담을 수 있을 때의 최대 가치”
• 각 물건(무게 w, 가치 v)을 하나씩 확인하면서,
  현재 가방 한도(K)부터 물건의 무게(w)까지 역순으로 갱신한다.

뒤에서부터 갱신해야 한 물건을 여러 번 사용하는 일이 없기 때문이다.
(→ 앞에서부터 채우면 ‘무한히 재사용 가능한 배낭’ 형태가 되어버림)

---

DP 정의 & 점화식

dp 정의

• dp[i]: 무게 i까지 담을 수 있을 때의 최대 가치

---

초기값

• 처음에는 어떤 물건도 담지 않았으므로
  dp[0] = 0 (나머지는 자동으로 0으로 초기화됨)

---

점화식

각 물건 (w, v)에 대하여,
현재 용량 j를 뒤에서부터 갱신한다.

dp[j] = max(dp[j], dp[j - w] + v)
단, j >= w일 때만 가능하다.

---

최종 답

최대 배낭 용량 k일 때의 최대 가치는
dp[k] 이다.

---

전체 코드 (제출용)

package A5DP.Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class G12865평범한배낭 {
    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[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken()); // 무게
            arr[i][1] = Integer.parseInt(st.nextToken()); // 가치
        }

        int[] dp = new int[k + 1]; // dp[i]: 무게 i까지의 최대 가치

        for (int i = 0; i < n; i++) {
            int w = arr[i][0];
            int v = arr[i][1];
            for (int j = k; j >= w; j--) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }

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