[Algorithms] 동적 계획법(Dynamic Programming)-가방문제(냅색 알고리즘)

 

 

• 처음 문제를 읽었을 때 DFS로 풀면 좋겠다고 생각해서 코드를 짯으나 다른 테스트 케이스에서 time limit에 걸려버렸다. 생각해보니 가방의 저장무게가 만약에 1000kg라고 하고 특정 보석이 1kg이라고 하면 1000번까지 돌면서 경우를 봐야하는 것인데 시간이 초과 될만했다. 밑에는 DFS로 푼 코드  

def DFS(start, sum, res):
    global res_
 
    if res > res_:
        res_=res
 
    for i in range(start,n):
        if sum+jewelry[i][0] <= m:
            DFS(i, sum+jewelry[i][0], res+jewelry[i][1])
 
if __name__=='__main__':
 
    n, m = map(int, input().split())
    jewelry = [list(map(int, input().split())) for _ in range(n)]
    jewelry.sort(reverse=True)
 
    res_ = -2147000000
    for i in range(n):
        DFS(i, 0, 0)
 
    print(res_)
 

 

 

 

 

• 그렇다면 우리가 공략해야 할 것은 다이나믹 프로그래밍! 코드 라인도 줄어들고 시간복잡도가 확 줄어든 것을 보면서 알고리즘의 중요성을 다시 한번 느끼게 되었다.

if __name__=='__main__':
 
    n, m = map(int, input().split())
    jewel = [list(map(int, input().split())) for _ in range(n)]
    dyn = [0]*(m+1)
 
    for kg, val in jewel:
        for i in range(kg, m+1):
            dyn[i] = max(dyn[i], dyn[i-kg] + val)
            
    print(dyn[m])