[백준] 12865 - 평범한 배낭

1. 문제 요약

• 물건 N개 (각각 무게 W, 가치 V)
• 최대 무게 K
• 가치의 합이 최대가 되도록 물건 선택

👉 단, 각 물건은 한 번만 선택 가능 (0/1 배낭)

---

2. 처음 접근 (실패 이유)

처음에는 이런 식으로 생각했다:

• 각 물건마다 “최적의 조합 하나”만 저장
• 이전 결과랑 비교해서 갱신

하지만 이 방식은 틀렸다.

🚨 왜 틀릴까?

배낭 문제는 한 시점에서도 여러 선택지가 필요하다.

예를 들어:

조합가치무게

A	10	5
B	9	3

👉 지금 보면 A가 더 좋아 보이지만
👉 나중에 물건을 추가하면 B가 더 유리할 수도 있음

즉,

❗ “현재 최적 하나만 남기면 미래의 최적을 놓칠 수 있다”

---

3. 핵심 아이디어

🔥 DP 정의

 

dp[j] = 무게가 j일 때 얻을 수 있는 최대 가치

---

4. 점화식

현재 물건 (w, v)를 고려할 때:

 

dp[j] = max(dp[j], dp[j - w] + v)

 

의미:

• dp[j] → 현재 물건을 선택하지 않는 경우
• dp[j - w] + v → 현재 물건을 선택하는 경우

👉 둘 중 더 큰 값을 선택

---

5. 가장 중요한 포인트

⚠️ 반드시 뒤에서부터 갱신해야 한다

 

for j in range(k, w - 1, -1):

 

이유

앞에서부터 하면:

for j in range(w, k + 1):

 

👉 같은 물건을 여러 번 사용하게 됨
👉 무한 배낭 문제가 됨

---

6. 전체 코드

 

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
dp = [0] * (k + 1)

for _ in range(n):
    w, v = map(int, input().split())
    for j in range(k, w - 1, -1):
        dp[j] = max(dp[j], dp[j - w] + v)

print(dp[k])