[DP] 평범한 배낭 - 백준

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

12865번: 평범한 배낭

 

Knapsack 문제의 전형적인 예시다. 

 

메모이제이션을 이용하여 recursion을 통해 구현하였다. 

 

본 문제는 정석적인 문제라 형태를 외워놔도 좋을 것 같다. 

 

n, k = [int(x) for x in input().split()]

weight = []; value = []; dic = {};
for _ in range(n) :
    w, v = [int(x) for x in input().split()]
    weight.append(w)
    value.append(v)
    
def knapsack(k, n, memo={}) :
    if (k, n) in memo :
        return memo[(k,n)]
		### 모든 무게를 소진했거나 아이템을 소진한 경우
    if k == 0 or n == 0 :
        return 0
		## 무게가 넘어가는 경우
    if weight[n-1] > k :
				## 단순하게 물건 제거
        memo[(k,n)] = knapsack(k,n-1)
        return memo[(k,n)]
    else :
				### 무게를 실을 수 있는 경우, 실은 경우랑 그렇지 않은 경우랑 비교해서 최대값 넣음
        memo[(k, n)] = max(value[n-1]+knapsack(k-weight[n-1], n-1),knapsack(k,n-1))
        return memo[(k, n)]

print(knapsack(k,n))