[백준] 평범한 배낭(12865번) - Python

✅문제 - 평범한 배낭(12865번)

---

 

✅필요 알고리즘 개념 - 다이나믹 프로그래밍(Dynamic Programming)

---

🔵What is Dynamic Programming ?

        ◼다이나믹 프로그래밍이란 한 번 해결된 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시

           계산하지 않도록 하는 기법이다.

        ◼Dynamic Programming Table 을 만들어 상태를 이전 결과들을 저장한다.

        ◼푸는 방식은 크게 2가지 방법으로 바텀업/탑다운 방식으로 풀고 탑다운 방식은 주로 재귀함수를 이용             한다.

 

 

✅코드

---

import sys

input = sys.stdin.readline

n,k = map(int,input().rstrip().split())
stuff = [(0,0)]+[tuple(map(int,input().rstrip().rsplit())) for _ in range(n) ]

dp = [0 for _ in range(k+1)]

for i in range(1,n+1):
    for j in range(k,0,-1):
        weight = stuff[i][0]
        value  = stuff[i][1]

        if weight > j:
            break
        else:
            dp[j] = max(dp[j],dp[j-weight]+value)

print(dp[k])

 

✅코드 설명

---

 

for i in range(1,n+1):
    for j in range(k,0,-1):
        weight = stuff[i][0]
        value  = stuff[i][1]

        if weight > j:
            break
        else:
            dp[j] = max(dp[j],dp[j-weight]+value)

반복문을 이해하는 것이 가장 중요하다. 

이때 i 의 값은 stuff의 인덱스 이다.

weight는 현재 추가하려는 물건의 무개

value는 현재 추가하려는 물건의 값어치가 된다.

 

j의 값은 용량(배낭에 넣을 수 있는 무게)이고 k 부터 1까지 내려가는 방식을 사용했다.

❗❗❗이 부분이 바로 포인트이다 !

이런 무게 제한처럼 limit이 있는 경우의 문제는 제한 부터 내려오는 방법을 사용하는 것이 구현하기에 좋다.

 

if 문에서 배낭의 용량 보다 weight가 더 큰 경우에는 물건을 넣을 수 없으므로 반복문을 종료한다.

 

j > weight인 경우가 중요하다.

dp[j] = max(dp[j-weight] + value, dp[j])

dp[j-weight] + value는 현재 물건을 넣었을 때의 value가 되고 이를 dp[j] 기존에 저장 돼있던 value의 최대값과 비교한다.