백준 알고리즘 - 평범한 배낭(12865번)[Python]

문제

문제 이미지 넣기

문제 상황

- 여러가지의 선택지가 있고 어떤 선택이 다른 선택에 영향을 주어 최선의 결과를 찾을 때 DP를 사용한다.

 

해결 전략

- 어떤 선택이 다른 선택에 영향을 주기 때문에 dp 사용

코드 

n, k = map(int, input().split()) # 물품의 수, 버틸 수 있는 무게 입력
cache = [[0]*(k+1) for _ in range(n+1)] # cache 가 for문 안에 들어가면 안된다.
# 리스트 컴프리핸션 숙지
for i in range(1, n+1):
    w, v = map(int, input().split()) # weight, value
    for j in range(1, k+1):
        if w > j:
            cache[i][j] = cache[i-1][j]
        else :   
            cache[i][j] = max(cache[i-1][j], cache[i-1][j-w] + v)
 
print(cache[n][k])

 

해설

새로 학습한 것 & 실수

- 반복 학습 필요