12865

Question

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))을 하네욥..!

코딩 센세 · Answer

좋은 질문해주셔서 감사합니다 :)   배낭 문제를 이야기 하기 전에 상담 문제로 먼저 설명 드리겠습니다!   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일 때 계산했을 때, 최대한으로 담을 수 있는 가치는 얼마인가? 에 대한 정답이 담기게 되는 겁니다!   이해 안되면 또 답글 달아주세요 :)