[김태원 알고리즘] 가방문제 (냅색 알고리즘, DP)

사용 언어: Python3

문제

풀이

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

# dp : 가방의 최대 저장무게가 index라고 할 때, 담을 수 있ㄴ는 보석의 최대 "가치"
dp = [0] * (limit + 1)
for w, v in lst: # (weight, value)
    for j in range(w, limit + 1):
        dp[j] = max(dp[j], dp[j-w] + v) # ✅ 새로 계산한 값이 더 큰 경우에만 업데이트

print(dp[limit]) # 가방의 limit이 문제에서 주어진 limit일 때

• max(dp[j], dp[j-w] + v) 추가 설명
  • dp[j]: (w, v) 보석 적용 전 최대 가치
  • dp[j-w]: (w, v) 보석 적용 후 최대 가치
    • dp[j-w]인 이유 : 무게가 w인 보석을 담을 것이기 때문에 그 무게(w)만큼 비워두어야 한다

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기