[TIL] knapsack 알고리즘 (배낭 문제)

knapsack problem

 - 배낭 문제 : 배낭에 담을 수 있는 무게의 최댓값은 정해져 있고 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 넣을 짐을 고르는 방법을 찾는 문제

 

 

냅색 알고리즘은 물건 분할 유무에 따라 분할 가능한 문제와 0-1 문제로 나뉜다.

여기서 다룰 문제는 0-1 냅색 알고리즘으로

백준 12865 문제를 풀다가 접하게 되었다.

 

12865번: 평범한 배낭 (acmicpc.net)

12865번: 평범한 배낭

 

DP알고리즘에 속한 문제인데 앞서 풀었던  LIS나 LCS와 비슷하다.

이해하기 쉽도록 표를 그려보았다.

 

주어지는 무게-가치 리스트는 [[6,13], [4,8], [3,6], [5,12]]이며

배낭이 담을 수 있는 최대 무게는 7이다.

 

2차원 배열을 사용할 때 X축에는 무게의 범위를 Y축에는 물건의 개수만큼 배열을 만들어준다.

이제 알고리즘을 적용할 차례이다.

1. 현재 물건이 해당하는 무게보다 작은 경우 ->  [i-1][j]를 입력한다.

2. 현재 물건이 해당하는 무게보다 같거나 큰 경우 2-1과 2-2의 가치 중 더 큰 값을 입력한다.

     2-1. 현재 물건을 넣어준 후 남은 무게를 채울 수 있는 최댓값을 가져온다.

     2-2. 현재 물건을 넣어주는 것보다 다른 물건들로 채우는 값을 가져와 넣어준다.

 

2의 경우를 자세히 보자.

무게-가치가 [3,6]이고 무게 7을 돌고 있다면

현재 물건의 무게는 3이므로 더 넣을 수 있는 무게는 4

현재 가치는 6이므로 더 넣을 수 있는 무게 4의 가치는 8

따라서 가치 6과 8을 더하면 14이다.

이때, 14는 이전까지 모든 경우의 수

(현재 물건이 아닌 물건의 가치로 채우는 경우, 여기서는 [4,8]이 7을 돌 때의 가치 13이 해당)

에서의 최댓값에 해당하므로 이 값을 넣어준다.

이를 식으로 정리한다면 다음과 같다.

 

knapsack[i][j] = max(value(현재 물건의 가치 )+ knapsack[i-1][j-weight], knapsack[i-1][j])

 

이제 정리한 알고리즘을 바탕으로 코드를 짜면 다음과 같다.

 

import sys

n,k = map(int, input().split())

lst=[[0,0]]
knapsack = [[0 for _ in range(k+1)] for _ in range(n+1)]

for _ in range(n):
    lst.append(list(map(int, input().split())))
    
for i in range(1, n+1):
    for j in range(1,k+1):
        w = lst[i][0]
        v = lst[i][1]
        
        if j < w:
            knapsack[i][j] = knapsack[i-1][j]
        else:
            knapsack[i][j] = max(v+ knapsack[i-1][j-w], knapsack[i-1][j])

print(knapsack[n][k])