[백준] 12865. 평범한 배낭 - Python

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

12865번: 평범한 배낭

---

• 생각
  • DP
  • 거꾸로 계산
    • 가치 최대치부터
  • 이 물건을 담는 것과 담지 않는 것중 가치가 큰 거 찾기
• 코드

# 물품의 수, 버틸 수 있는 무게
n, k = map(int, input().split())

# 여행에 필요하다고 생각하는 물건들
items = [list(map(int,input().split())) for _ in range(n)]
dp = [0 for _ in range(k+1)]

for item in items:
    # 무게, 가치
    w,v = item
    for i in range(k,w-1,-1):
        # 이 물건을 담지 않기 / 담기 중 가치가 큰 거 선택
        dp[i] = max(dp[i],dp[i-w]+v)

print(dp[k])