[문제] 백준 12865 평범한 배낭

✅ 알고 가기

Knapsack 문제(배낭 문제)는 알고리즘 문제에서 자주 등장하는 유형이다.
유형에 따라 동적 프로그래밍(DP) 또는 그리디(Greedy) 방식으로 풀이한다.

• 각각의 물건은 무게(weight)와 가치(value)를 가짐
• 무게 제한(capacity)이 있는 배낭에 물건을 담을 때
• 총 무게를 넘기지 않으면서 가치의 총합을 최대화하는 것이 목표

항목	0/1 Knapsack	Fractional Knapsack
물건 쪼갤 수 있음?	❌ No (넣거나 안 넣거나)	✅ Yes (일부만 담기 가능)
풀이 방식	DP	Greedy
시간 복잡도	O(nW)	O(n log n)
중복 가능?	❌	✅ (부분 가능)
대표 문제	백준 12865	이론 위주, 자주 출제

---

1️⃣ 0/1 Knapsack (DP)

• 각 물건을 넣거나 안 넣거나 두 가지 선택
• dp[w] = 무게 w일 때 만들 수 있는 최대 가치
• 중복 사용 방지를 위해 역순으로 갱신

def knapsack_01_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]

weights = [3, 4, 5]
values = [30, 50, 60]
capacity = 8

print(knapsack_01_optimized(weights, values, capacity))  # 출력: 90

---

2️⃣ Fractional Knapsack (Greedy)

• 물건을 쪼갤 수 있으니 가치/무게 비율이 높은 것부터 채우기
• 공간이 부족하면 일부분만 넣기

def knapsack_fractional(weights, values, capacity):
    n = len(weights)
    items = [(values[i]/weights[i], weights[i], values[i]) for i in range(n)]
    items.sort(reverse=True)  # 비율 높은 순

    total_value = 0.0
    for ratio, weight, value in items:
        if capacity >= weight:
            capacity -= weight
            total_value += value
        else:
            total_value += ratio * capacity
            break

    return total_value

weights = [3, 4, 5]
values = [30, 50, 60]
capacity = 8

print(knapsack_fractional(weights, values, capacity))  # 출력: 98.0

---

✅ 문제 풀이

다시 문제로 돌아와서, 백준 12865번 평범한 배낭 문제를 보자.
0/1 Knapsack problem임을 쉽게 알아차릴 수 을 것이다.

이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

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

4 7
6 13
4 8
3 6
5 12

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

14

여기에서 아이디어를 내보자.

2차원 dp) dp[i][w] = i번째 물건까지 고려했을 때, 무게 w로 만들 수 있는 최대 가치
dp[i][w]는 반드시 바로 위 행(i-1)의 값만 참조하기에,
이전에 처리한 자기 자신(i행)의 값은 절대 참조하지 않으므로 순방향 탐색해도 상관없다.

1차원 dp) dp[w] = 무게 w일 때 만들 수 있는 최대 가치
갱신된 값이 다시 참조되면 같은 물건을 여러 번 넣는 결과가 되므로,
각 물건마다 그 물건을 썼을 때/안 썼을 때를 제대로 고려하기 위해서는 무게를 역순으로 반복해야한다.

주의) 무게를 역순으로 반복한다는 말은 무거운 물건부터 넣어보겠다는 말이 아니다.
0/1 Knapsack의 본질은 **모든 조합을 시도**하면서 최적해를 쌓아가는 방식으로,
어떤 물건을 먼저 넣고 나중에 넣고는 전혀 중요하지 않다. (sorting 불필요)

아이디어를 코딩으로 옮겨보자.
2차원 dp와 1차원 dp의 점화식 구조는 동일하지만, dp[i][w] vs dp[w] 차이만 다르다.
2차원 dp의 직관성이 더 높으므로 이해를 할 때는 이 코드를 먼저 보고,
메모리나 속도 측면에서 유리한 1차원 dp 형식으로 코드 쓰는 걸 연습해보자.

# 2차원 dp
# dp[0][w]: 아무 물건도 고려하지 않았을 때 → 모두 0
# dp[i][0]은 무게가 0일 때 i번째 물건까지 고려했을 때 만들 수 있는 최대 가치 → 모두 0
# 행 개수 = 물건 수 + 1 (0번 물건부터 n번까지)
# 열 개수 = 최대 무게 K + 1 (0부터 K까지)

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = [[0] * (K + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    weight, value = items[i - 1]
    for w in range(K + 1):
        if weight <= w:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value)
        else:
            dp[i][w] = dp[i - 1][w]

print(dp[N][K])

# 1차원 dp

import sys

N, K = map(int, sys.stdin.readline().split())
items = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0] * (K + 1)

for weight, value in items:
    for w in range(K, weight - 1, -1): # 역방향 탐색 (같은 물건 반복 사용 방지)
        dp[w] = max(dp[w], dp[w - weight] + value)

print(dp[K])

1차원 dp를 기준으로 예시 입력과 출력을 실행해보자.
계산 과정을 이해하기 쉽도록 순방향으로 써놨지만, 코드 상으로는 역방향으로 갱신한다는 점을 주의하자.

물건	무게	가치
A	6	13
B	4	8
C	3	6
D	5	12

• 초기 상태:

  dp = [0, 0, 0, 0, 0, 0, 0, 0]

• A 넣을 수 있는 경우 (w ≥ 6):

  dp[6] = max(dp[6], dp[0] + 13) → 13
  dp[7] = max(dp[7], dp[1] + 13) → 13

• B 넣기 (w ≥ 4):

   dp[4] = max(dp[4], dp[0] + 8) → 8
   dp[5] = max(dp[5], dp[1] + 8) → 8
   dp[6] = max(13, dp[2] + 8) → 13
   dp[7] = max(13, dp[3] + 8) → 13

• C 넣기 (w ≥ 3):

  dp[3] = max(0, dp[0] + 6) → 6
  dp[4] = max(8, dp[1] + 6) → 8
  dp[5] = max(8, dp[2] + 6) → 8
  dp[6] = max(13, dp[3] + 6) → 13
  dp[7] = max(13, dp[4] + 6) → 14
  ```-

• D 넣기 (w = 5 ~ 7)

  dp[5] = max(8, dp[0] + 12) = max(8, 12) → 12
  dp[6] = max(13, dp[1] + 12) = max(13, 12) → 13
  dp[7] = max(14, dp[2] + 12) = max(14, 12) → 14

• 최종 결과:

  dp = [0, 0, 0, 6, 8, 8, 13, 14]

• 출력

  dp[7] = 14

무게 제한이 있는 배낭 + 쪼갤 수 없는 물건 → 0/1 Knapsack
시간 복잡도: O(NK) → N=100, K=100,000까지 가능
공간 복잡도: O(K) (1차원 DP) / O(NK) (2차원 DP)