DP(동적 계획법, Dynamic Programming ) - 배낭 이론 정리

1️⃣ 배낭 문제의 종류

배낭 문제는 크게 3가지로 나뉩니다.

📌 1. 0/1 배낭 문제 (0/1 Knapsack Problem)

✔ 각 물건은 한 번만 넣을 수 있음 (0 또는 1의 선택)
✔ 즉, 특정 물건을 "선택하거나 안 하거나" 결정해야 함
✔ DP를 활용하여 최적해를 찾음

📌 2. 무제한 배낭 문제 (Unbounded Knapsack Problem)

✔ 각 물건을 여러 번 선택할 수 있음 (무한히 넣을 수 있음)
✔ 주로 "동전 거스름돈 문제"와 유사한 DP 방식 사용

📌 3. 부분 배낭 문제 (Fractional Knapsack Problem)

✔ 각 물건을 부분적으로 쪼개서 넣을 수 있음
✔ 탐욕법(Greedy Algorithm)을 사용하여 해결 가능

---

2️⃣ 0/1 배낭 문제 (DP)

✔ 주어진 N개의 물건과, W라는 무게 제한이 있는 배낭이 있음
✔ 각 물건은 (무게, 가치)로 표현됨
✔ 최대 가치를 얻을 수 있도록 배낭을 채우는 방법 찾기

---

✅ 0/1 배낭 문제의 점화식

DP 테이블 정의

• dp[i][w]: i번째까지의 물건을 고려했을 때, 배낭 무게 w에서 얻을 수 있는 최대 가치

점화식
✔ 물건 i를 배낭에 넣지 않는 경우:

dp[i][w]=dp[i−1][w]dp[i][w] = dp[i-1][w]

✔ 물건 i를 배낭에 넣는 경우:

dp[i][w]=max⁡(dp[i−1][w],dp[i−1][w−weight[i]]+value[i])dp[i][w] = \max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

✔ 즉, i번째 물건을 선택할지 말지를 결정하는 문제!

---

✅ 0/1 배낭 문제 코드 (2차원 DP)

N, W = map(int, input().split())  # 물건 개수, 배낭 최대 무게
items = [list(map(int, input().split())) for _ in range(N)]  # (무게, 가치) 리스트

# DP 테이블 초기화
dp = [[0] * (W + 1) for _ in range(N + 1)]

# DP 계산
for i in range(1, N + 1):
    weight, value = items[i - 1]
    for w in range(W + 1):
        if w < weight:
            dp[i][w] = dp[i - 1][w]  # 물건을 넣을 수 없는 경우
        else:
            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight] + value)

# 결과 출력
print(dp[N][W])

✔ 시간 복잡도: O(N × W)
✔ 공간 복잡도: O(N × W)

---

3️⃣ 0/1 배낭 문제의 1차원 DP 최적화

✔ dp[w] 만을 이용하여 이전 값을 업데이트
✔ 뒤에서부터 업데이트해야 중복 계산을 방지!
✔ 시간 복잡도는 O(N × W), 공간 복잡도 O(W)로 최적화 가능

✅ 1차원 DP 코드

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

dp = [0] * (W + 1)

for weight, value in items:
    for w in range(W, weight - 1, -1):  # 뒤에서부터 업데이트!
        dp[w] = max(dp[w], dp[w - weight] + value)

print(dp[W])

✔ 공간 복잡도: O(W)
✔ 배열 하나만 사용하여 최적화! 🚀

---

4️⃣ 무제한 배낭 문제 (Unbounded Knapsack)

✔ 각 물건을 여러 번 선택할 수 있음
✔ 동전 거스름돈 문제와 유사함

✅ 점화식 (1차원 DP)

dp[w]=max⁡(dp[w],dp[w−weight]+value)dp[w] = \max(dp[w], dp[w - weight] + value)

✔ 이전 값을 사용하지 않고, 같은 행에서 바로 업데이트 가능

✅ 코드

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

dp = [0] * (W + 1)

for weight, value in items:
    for w in range(weight, W + 1):  # 앞에서부터 업데이트
        dp[w] = max(dp[w], dp[w - weight] + value)

print(dp[W])

✔ 앞에서부터 업데이트해야 중복 계산이 반영됨
✔ 시간 복잡도 O(N × W), 공간 O(W)

---

5️⃣ 0/1 배낭 vs 무제한 배낭 차이

유형 제한 사항 점화식

0/1 배낭	각 아이템을 한 번만 선택 가능	dp[w] = max(dp[w], dp[w - weight] + value) (뒤에서부터)
무제한 배낭	각 아이템을 여러 번 선택 가능	dp[w] = max(dp[w], dp[w - weight] + value) (앞에서부터)

---

6️⃣ 부분 배낭 문제 (Fractional Knapsack)

✔ 물건을 부분적으로 쪼개서 넣을 수 있음
✔ 그리디(Greedy) 알고리즘으로 해결 가능

✅ 알고리즘

1. 각 물건의 가치/무게 비율을 계산
2. 가치가 높은 순서대로 배낭에 담음
3. 더 이상 담을 수 없으면 일부만 넣음

✅ 코드

N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]  # (무게, 가치)

# 가치/무게 비율로 정렬
items.sort(key=lambda x: x[1] / x[0], reverse=True)

total_value = 0
for weight, value in items:
    if W >= weight:
        W -= weight
        total_value += value
    else:
        total_value += value * (W / weight)
        break

print(total_value)

✔ 시간 복잡도: O(N log N) (정렬 사용)
✔ 그리디 방법으로 최적의 해를 구할 수 있음

---

✅ 최종 정리

✔ 0/1 배낭 (DP 사용)

• 각 물건을 한 번만 선택
• dp[w] = max(dp[w], dp[w - weight] + value) (뒤에서부터 업데이트) ✔ 무제한 배낭 (DP 사용)
• 각 물건을 여러 번 선택 가능
• dp[w] = max(dp[w], dp[w - weight] + value) (앞에서부터 업데이트) ✔ 부분 배낭 (그리디 사용)
• 물건을 부분적으로 넣을 수 있음
• "가치/무게 비율"을 기준으로 정렬 후 선택