[Algorithms] 동적 계획법(Dynamic Programming)-최대 점수 구하기(냅색 알고리즘)

 

• 앞에서 진행했었던 가방문제와 동일하다고 생각할 수 있으나, 한 유형당 문제 한 개만 풀 수 있다는 점이 다르다. 가방문제에서는 보석 각 타입을 무한정으로 이용할 수 있었다 
• 상황을 이해하기 위해 우선 2차원 배열로 이해해보자 

• 문제를 중복해서 풀지않기 위해서 2차원 배열로 풀어냈는데, 이는 1차원 배열로도 설명이 가능하다

 

 

 

위의 1차원 배열 코드 구현은 공간복잡도 시간복잡도 모두 고려했기 때문에 아주 최적이다

 

if __name__=='__main__':
 
    n, m = map(int, input().split())
    dyn = [0]*(m+1)
 
    for i in range(1, n+1):
        scr, min = map(int, input().split())
        for j in range(m, min-1, -1):
            dyn[j] = max(dyn[j], dyn[j-min]+scr)
 
    print(dyn[m])