[오늘의 백준 문제] 12865번 평범한 배낭 - 배낭 문제, DP

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

 

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

4 7
6 13
4 8
3 6
5 12

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

14

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

 

 

---

이 문제는 배낭(Knapsack) 문제 중 가장 유명한 문제이다.

---

📦 배낭(Knapsack) 문제란?

 

배낭 문제는 조합 최적화 문제 중 하나로, 다음과 같은 조건 하에서 가치의 최댓값을 구하는 문제다.

• N개의 물건이 주어짐
• 각 물건은 무게 W, 가치 V 속성을 가짐
• 배낭의 최대 허용 무게는 K
• 이 배낭에 담을 수 있는 물건들을 선택하여, 총 가치의 합이 최대가 되도록 하는 것이 목표

---

🎯 배낭 문제의 종류

유형	설명	중복 허용	알고리즘 핵심
0/1 배낭 문제	각 물건을 한 번만 담을 수 있음	❌	dp[j] = max(dp[j], dp[j - W] + V)
무제한(완전) 배낭 문제	각 물건을 무제한으로 담을 수 있음	✅	for j = W to K (앞에서부터 순회)
다중 배낭 문제	각 물건이 정해진 개수만큼 있음	제한적 허용	이진 분할 + 0/1로 변환
분할 배낭 문제 (Fractional)	물건을 쪼개서 담을 수 있음	✅	Greedy (가치/무게 비율 기준 정렬)

 

위 문제의 경우, 각 물건을 한 번만 담을 수 있고, 쪼개서 담을 수 없기 때문에 0/1 배낭 문제 유형이다.

---

🧠 0/1 배낭 문제 핵심 개념 (가장 많이 나옴)

 

1. 상태 정의

• dp[i][j]: i번째 물건까지 고려했을 때, 무게 j로 만들 수 있는 최대 가치
  • i는 1부터 N까지, j는 0부터 K까지
• dp[j]: 배낭의 용량이 j일 때, 담을 수 있는 최대 가치

 

2. 점화식

• 담을 수 없는 경우 → 물건을 넣지 않음
• 담을 수 있는 경우 → 물건을 넣지 않는 경우와 넣는 경우 중 최대값을 선택
  • 물건을 넣지 않음: dp[i - 1][j] 또는 dp[j]
  • 물건을 넣음: dp[i - 1][j - W[i]] + V[i] 또는 dp[j - W[i]] + V[i]

for (int i = 0; i < N; i++) {
    for (int j = 0; j <= K; j++) { // 0 ~ K
        int w = W[i];
        int v = V[i];
        
        if (w > j) { // 현재 물건을 담을 수 없는 경우
            dp[i][j] = dp[i - 1][j];
        } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
        }
    }
}

 

위 코드를 다음과 같이 1차원 DP로 최적화 할 수 있다.

for (int i = 0; i < N; i++) {
    int w = W[i];
    int v = V[i];
    
    // 1차원으로 최적화 시, j는 K → w 로 감소하면서 순회해야 함!
    for (int j = K; j >= w; j--) {
        dp[j] = Math.max(dp[j], dp[j - w] + v);
    }
}

 

🤨 왜 뒤에서부터 순회해야 하는가?

• 동일한 물건을 한 번만 담을 수 있어야 하므로!
• 앞에서부터 하면, 같은 물건을 여러 번 담게 되는 문제가 생김 (중복)

---

⏱️ 시간복잡도

• O(N * K) (N: 물건 수, K: 최대 무게)
• 최적화하면 1차원 배열만으로 구현 가능

---

📜 자바 코드

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 maxWeight = Integer.parseInt(st.nextToken()); // 최대 무게

        int[] dp = new int[maxWeight + 1];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken()); // 물건 무게
            int value = Integer.parseInt(st.nextToken());  // 물건 가치

            // 뒤에서부터 순회해야 같은 물건을 여러 번 담지 않음
            for (int j = maxWeight; j >= weight; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight] + value);
            }
        }

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