[보기 쉬운 Algorithm] 냅색(Knapsack) 알고리즘 - Python

<설명>

냅색 알고리즘은 DP(Dynamic Programming)의 한 종류로 많이 쓰이는 방식 중 하나이다.

가방문제에 가장 많이 등장한다!

 

가방에 담을 수 있는 무게 제한이 있고, 각각의 물건은 무게와 가치가 있다. 가방의 무게를 초과하지 않게 물건을 많이 담아 최고 가치를 가지게 하는 문제이다.

 

<구현>

for i in range(1, n+1):
    for j in range(1, k+1):
        w = thing[i][0]   # 물건의 무게
        v = thing[i][1]   # 물건의 가치

        if j < w:   # 현재 무게가 물건 보다 작다면
            table[i][j] = table[i-1][j]  # 위의 값을 그대로
        else:
            table[i][j] = max(table[i-1][j], table[i-1][j-w]+v)

 

 

<예시 문제>

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

9251번: LCS

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

12865번: 평범한 배낭