12865

def recur(idx, weight):
    if weight > K :
        return -99999
    if idx == N :
        return 0 
    if dp[idx][weight] != -1:
        return dp[idx][weight]
    
    dp[idx][weight] = max(recur(idx + 1, weight + items[idx][0]) + items[idx][1], recur(idx + 1, weight))
    return dp[idx][weight]

N,K = map(int,input().split())
items = [list(map(int,input().split())) for _ in range(N)]
#무게를 고려해서 가치를 담는 dp테이블, 무게는 얼마든지 커질 수 있으므로 10만, 그리고 물건개수만큼 N 작성
dp = [[-1 for _ in range(100_001)] for _ in range(N)]

print(recur(0,0))

recur(0,0) 재귀함수를 불렀는데 dp 테이블의 최대값이 찍히는게 잘 이해되지 않습니당...!
당연히 dp테이블에서 max값을 찾아 출력해야 하는 줄 알았는데, 코드를 보니 그냥 print(recur(0,0))을 하네욥..!

좋은 질문해주셔서 감사합니다 :)

배낭 문제를 이야기 하기 전에 상담 문제로 먼저 설명 드리겠습니다!

DP 테이블이 0에서 7까지 있다고 하면 , 7일은 이미 퇴사한 뒤라서 return 0 을 해주고,

그 이후는 무시하도록 -999999... 를 넣어주는 코드를 짰습니다.

처음에 저희가 recur(0)을 하게 되면, 재귀 함수는 idx 0부터 시작해서 모든 경우의 수를 탐색하겠죠?

그리고 idx 7에 도착한다면 return 0을 해줄거고, idx 7이상에 도착한다면 return -99999를 해줄겁니다.

그 이후에는 어떻게 되나요?

아래에 작성하신 코드대로, return을 해서 가져온 값들을 비교하면서, 그 중에서 더 큰 값을 해당 테이블에 저장하고 return하겠죠?

dp[idx][weight] = max(recur(idx + 1, weight + items[idx][0]) + items[idx][1], recur(idx + 1, weight))
 return dp[idx][weight]

그렇다면

dp테이블의 0번째 인덱스에 담기는 값은

1일 ~ 7일기준으로 받을 수 있는 가장 큰 급여

dp테이블의 6번째 인덱스에 담기는 값은

7일 ~ 7일 기준으로 받을 수 있는 가장 큰 급여

겠죠?

제 강의에서 아래와 같이 표를 이용해서 무게와 물건의 가치를 비교하면서 설명을 드렸습니다!

하지만 실제로 저 계산을 모두 한 뒤의 최댓값을 저장하는 DP 테이블에는

DP[0][0]은 배낭을 1번째 물건부터, 초기 무게가 0일때 계산했을 때, 최대한으로 담을 수 있는 가치는 얼마인가?에 대한 정답이 담기고,

DP[1][1]은 배낭을 2번째 물건부터, 초기 무게가 1일 때 계산했을 때, 최대한으로 담을 수 있는 가치는 얼마인가?에 대한 정답이 담기게 되는 겁니다!

이해 안되면 또 답글 달아주세요 :)

인프런 커뮤니티 질문&답변