[백준, 12865번] 평범한 배낭 - 냅색 알고리즘

냅색 알고리즘은 배낭에 담을 수 있는 무게의 최댓값이 정해지고, 일정 가치와 무게를 가진 짐을 배낭에 넣을 때
 가치의 합이 최대가 되도록 짐을 고르는 방법

그래서 푸는 과정으로는 x축으로는 가방의 무게, y축으로는 짐의 개수로 생각하고
 이전의 값을 참조하는 dp 문제로 모두 n+1, k+1로 배열과 반복문을 실행

이때 x축으로도 0의 무게에 대한 배낭, y축으로도 [0,0]을 따로 추가한 이유는 
 x축에 해당하는 0의 무게에 대한 배낭 값도 사용이 되기에 추가를 했음.
 ex) 배낭의 무게 j = 6, 실제 짐의 무게 6의 경우 6-6 = 0으로 0의 무게를 더하는 식이 되어야하는데 
 위의 식을 생각하지 못하면 -1인 k-1번째 무게를 가지기 때문.

이후 현재 반복문으로 탐색하는 가방의 현재 무게 j 보다 탐색하고 있는 현재 짐의 무게인 weight가 더 크다면 
 이전에 탐색했던 가치를 가져오고

만약 가방에 여유가 있어 짐을 넣을 수 있다면 아래의 두 가지 경우 중 큰 경우를 현재 dp의 값에 추가
 1. 현재 짐의 가치 + (탐색하는 가방의 현재 무게 j - 현재 짐의 무게)에 해당하는 가방 공간의 이전 짐 무게
 2. 이전 짐의 무게  

# 냅색 알고리즘 - 성공
import sys
input = sys.stdin.readline

n,k = map(int,input().split())
li = [[0,0]]+[list(map(int,input().split())) for _ in range(n)]

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

for i in range(1,n+1):
    weight, value = li[i]
    for j in range(1,k+1): dp[i][j] = dp[i-1][j] if j < weight else max(value+dp[i-1][j-weight], dp[i-1][j])
print(max(dp[n]))

 

처음 dp라는 것을 생각하지 않았을 때는 재귀로 풀 수 있을 것 같아서 풀었고 반례 같은 것도 잘 맞는데
 시간 초과가 나서 뭔가 이유를 알고 싶기도 하다.

# 재귀 - 시간 초과
def bag(i, wei,val):
    global m_weight, m_value, k
    if val > m_value and k >= wei: m_value = val
    elif wei > k: return
    for j in range(i, n):
        bag(j+1,li[j][0]+wei,li[j][1]+val)
        
import sys
input = sys.stdin.readline
n,k = map(int,input().split()) # 개수, 최대 무게
li = [ list(map(int,input().split())) for _ in range(n)] # 무게, 가치
m_value = 0
bag(0,0,0)
print(m_value)